Za co odpowiada ta zmienna?

0

Witam,

Dostałem zadanie rekrutacyjne od pewnej firmy polegające na rozwiązaniu zadania z XIX Olimpiady informatycznej (dokładniej zadanie z III etapu - "Pensje").
Rzecz jasna zasoby rozwiązanych prac są udostępnione, a ja mając wgląd w kod zwycięzców postanowiłem zacząć od jego analizy, żeby dokładnie zrozumieć jego działanie. Tutaj napotkałem pewien problem - dla rozjaśnienia sobie sprawy wpisałem w kilku miejscach funkcje wypisującą wartości poszczególnych tablic, ale przy jednej z nich za nic nie potrafię dojść skąd biorą się w niej wartości. Kod wygląda następująco:

#include <cstdio>
using namespace std;

#define MAXN 1000004

int n; // ilosc pracownikow
int przelozony[MAXN], pensja[MAXN]; // input
int uzyte[MAXN]; // ktore wartosci sa uzyte
int ile_podwladnych[MAXN];
int stopien[MAXN];
int podwladny[MAXN]; // bezposredni podwladny (jezeli tylko jeden)
int kolejka[MAXN], pocz = 0, kon = 0;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", przelozony + i, pensja + i);
        if (przelozony[i] == i) pensja[i] = n;
        if (pensja[i]) przelozony[i] = n+1;
    }
    ++n;
    przelozony[n] = n;
    pensja[n] = n;
        for (int i = 1; i < n; ++i) stopien[i] = 0;
    for (int i = 1; i < n; ++i)
        ++stopien[przelozony[i]]; // zliczamy bezposrednich
    for (int i = 1; i < n; ++i)
        if (stopien[i] == 0)
            kolejka[kon+1] = i;
    while (pocz < kon) {
        int akt = kolejka[pocz++];
        int przel = przelozony[akt];
        if (pensja[akt] == 0) {
            if (!--stopien[przel]) kolejka[kon++] = przel;
            ile_podwladnych[przel] += ile_podwladnych[akt] + 1;
        }
    }
        for (int i = 1; i < n; ++i)
        if (pensja[i])
            uzyte[pensja[i]] = i;
        else if (!podwladny[przelozony[i]])
                podwladny[przelozony[i]] = i;
             else podwladny[przelozony[i]] = -1;
    int i = 0;
    int ile_wolnych = 0, ile_mozliwych = 0;
    while (i < n-1) {
        while (i < n-1 && uzyte[i+1] == 0) { ++i; ++ile_wolnych; ++ile_mozliwych; }
        while (i < n-1 && uzyte[i+1] != 0) {
            ++i;
            int akt = uzyte[i], l = i;
            ile_wolnych -= ile_podwladnych[akt];
            if (ile_wolnych == 0) {
                while (ile_mozliwych-- && podwladny[akt] > 0) {
                     while (uzyte[l]) --l;
                     akt = podwladny[akt];
                     pensja[akt] = l;
                     uzyte[l] = akt;
                }
                ile_mozliwych = 0;
            }
            if (ile_podwladnych[akt] != 0)
                ile_mozliwych = 0;
        }
    }
    for (int i = 1; i < n; ++i)
        printf("%d\n", pensja[i]);
    return 0;
}

Sam problem dotyczy tablicy kolejka[] i zmiennej kon, których wartości zaznaczyłem na załączonym screenshotcie. Nie mam bladego pojęcia w jaki sposób to działa i pytanie kieruję do jakiejś mądrej głowy, która zechce mi pomóc screenshot.png

4

Ale przecież w dokumencie z olimpiady wszystko jest opisane.
Jest rozdział opisujący wzorcowe rozwiązania tego zadania.

4

Co ciekawe podane przez ciebie wzorcowe rozwiązanie, daje złą odpowiedź:
https://godbolt.org/z/Pd3nTMvPo
Nie uzupełnia danych, które można wywnioskować. Jesteś pewny, że skopiowałeś do forum właściwy kod, a nie jakąś swoją modyfikację?

3

Tak jak powiedział @MarekR22 przeczytaj opis rozwiązania z książeczki, jeśli nie będziesz rozumiał (nawet omówienia nie są łatwe do zrozumienia, do tego są pisane w miarę formalnym językiem) to zadawaj pytania i samemu próbuj pisać, na Szkopule możesz testować swoje rozwiązania. Kodu nie analizuj, pisz własny, ten najwyżej wykorzystaj do testowania.

1 użytkowników online, w tym zalogowanych: 0, gości: 1