Cod sursa(job #1019354)

Utilizator harababurelPuscas Sergiu harababurel Data 30 octombrie 2013 23:05:49
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#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;
}