Pagini recente » Cod sursa (job #118791) | Cod sursa (job #2663937) | Cod sursa (job #1646092) | Cod sursa (job #642141) | Cod sursa (job #3331337)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int t[1000009];
int rez[1000009];
long long a[1000009], b[1000009], c[1000009];
// Varianta recursiva (daca a mers la el, merge si la noi)
int root(int x){
if(x == t[x]) return x;
return t[x] = root(t[x]);
}
int main(){
int n;
if(!(fin >> n)) return 0;
// Initializare DSU
for(int i = 1; i <= n + 1; i++) t[i] = i;
// Citim prima pensula
fin >> a[1] >> b[1] >> c[1];
// ETAPA 1: Generarea (ATENTIE LA i-ul de aici)
for(int i = 2; i < n; i++){
a[i] = (1ll * a[i - 1] * i) % n;
b[i] = (1ll * b[i - 1] * i) % n;
c[i] = (1ll * c[i - 1] * i) % n;
}
// ETAPA 2: Procesarea Inversa (de la n-1 la 1)
for(int i = n - 1; i >= 1; i--){
int st = min(a[i], b[i]);
int dr = max(a[i], b[i]);
// Celulele noastre sunt de la 1 la n-1.
// Daca st e 0, il urcam la 1.
if(st == 0) st = 1;
// DSU jump
for(int j = root(st); j <= dr; j = root(j)){
rez[j] = (int)c[i];
t[j] = j + 1; // "Legam" celula de urmatoarea
}
}
// ETAPA 3: Afisarea (primele n-1 celule)
for(int i = 1; i < n; i++){
fout << rez[i] << '\n';
}
return 0;
}