Pagini recente » Cod sursa (job #1312832) | Cod sursa (job #3133120) | Cod sursa (job #2123396) | Cod sursa (job #2984659) | Cod sursa (job #3331333)
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("curcubeu.in");
ofstream out("curcubeu.out");
const int MAXN = 1000005;
// Tablourile pentru stocarea datelor (Offline)
int L[MAXN], R[MAXN], C[MAXN];
int Next[MAXN], solutie[MAXN];
int N;
// Functia find_next (DSU Iterativ - Fara recursie, fara Signal 11)
int find_next(int pos) {
int root = pos;
// Pasul 1: Gasim radacina (prima celula necolorata)
while (Next[root] != root) {
root = Next[root];
}
// Pasul 2: Path Compression (Aplatizam arborele pentru viteza)
int aux = pos;
while (Next[aux] != root) {
int next_node = Next[aux];
Next[aux] = root;
aux = next_node;
}
return root;
}
int main() {
// Viteza maxima pentru I/O
ios_base::sync_with_stdio(false);
in.tie(NULL);
long long Ar, Br, Cr;
if (!(in >> N >> Ar >> Br >> Cr)) return 0;
// ETAPA 1: Generarea si stocarea pensulelor
for (int i = 1; i < N; i++) {
L[i] = (int)(min(Ar, Br) + 1);
R[i] = (int)(max(Ar, Br) + 1);
C[i] = (int)Cr;
// Formulele de generare pentru pasul i+1
Ar = (Ar * (i + 1)) % N;
Br = (Br * (i + 1)) % N;
Cr = (Cr * (i + 1)) % N;
}
// ETAPA 2: Initializarea DSU
// Fiecare celula arata spre ea insasi (e libera)
for (int i = 1; i <= N + 1; i++) {
Next[i] = i;
}
// ETAPA 3: Procesarea INVERSA (de la ultima pensula la prima)
for (int i = N - 1; i >= 1; i--) {
// Cautam prima pozitie libera incepand de la L[i]
for (int j = find_next(L[i]); j <= R[i]; j = find_next(j)) {
solutie[j] = C[i];
// "Stergem" celula j unind-o cu j+1
// De acum, oricine ajunge la j va fi trimis la find_next(j+1)
Next[j] = find_next(j + 1);
}
}
// ETAPA 4: Afisarea rezultatului
for (int i = 1; i < N; i++) {
out << solutie[i] << "\n";
}
return 0;
}