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