Pagini recente » Cod sursa (job #556647) | Cod sursa (job #375422) | Cod sursa (job #351499) | Cod sursa (job #871304) | Cod sursa (job #1019354)
#include <iostream>
#include <fstream>
#define nmax 1000005
using namespace std;
bool root[nmax], used[nmax];
int hi[nmax], parent[nmax], v[nmax];
int A[nmax], B[nmax], C[nmax];
int n, pos, currentRoot, l, r;
void join(int R, int node) {
parent[node] = R;
hi[R] = max(hi[R], node);
root[node] = false;
}
int find(int node) {
if(root[node]) return node;
parent[node] = find(parent[node]);
return parent[node];
}
int main() {
ifstream f("curcubeu.in");
ofstream g("curcubeu.out");
f>>n>>A[1]>>B[1]>>C[1];
for(int i=2; i<n; i++) {
A[i] = (A[i-1] * i) % n;
B[i] = (B[i-1] * i) % n;
C[i] = (C[i-1] * i) % n;
}
for(int i=1; i<n; i++) {
root[i] = false; //asa vreau
parent[i] = i;
hi[i] = i;
}
for(int i=n-1; i>=1; i--) {
l = min(A[i], B[i]);
r = max(A[i], B[i]);
pos = l;
while(pos <= r && used[pos]) pos = hi[find(pos)] + 1; //gasesc prima pozitie necolorata
if(pos > r) continue;
currentRoot = pos;
root[currentRoot] = true;
used[currentRoot] = true;
hi[currentRoot] = currentRoot;
v[currentRoot] = C[i];
pos++;
while(pos <= r) {
if(root[pos]) { //am dat de o multime -> sar peste
pos = hi[find(pos)] + 1;
continue;
}
v[pos] = C[i];
used[pos] = true;
join(currentRoot, pos);
pos++;
}
}
for(int i=1; i<n; i++) g<<v[i]<<"\n";
return 0;
}