Cod sursa(job #1019372)

Utilizator harababurelPuscas Sergiu harababurel Data 30 octombrie 2013 23:37:57
Problema Curcubeu Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
//greu de inteles
#include <iostream>
#include <fstream>
#include <iomanip>
#define nmax 1000005
#define cout cout<<setw(2)
using namespace std;

int p[nmax], v[nmax];
int A[nmax], B[nmax], C[nmax];

int n, pos, currentRoot, l, r;

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++) p[i] = i;

    for(int i=n-1; i>=1; i--) {
        l = min(A[i], B[i]);
        r = max(A[i], B[i]);
        //cout<<l<<"->"<<r<<"\n";

        pos = l;
        while(pos <= r && v[pos] != 0) {
            if(p[pos] > 0) pos = p[pos];       //ma duc la radacina
            if(p[pos] < 0) pos = -p[pos] + 1;  //si ma mut la capatul drept + 1
        }

        if(pos > r) continue;

        currentRoot = pos;
        v[currentRoot] = C[i];
        p[pos] = -pos;
        pos++;


        while(pos <= r) {
            if(p[pos] != pos) {
                if(p[pos] > 0) pos = p[pos];
                p[currentRoot] = min(p[currentRoot], p[pos]);
                pos = -p[pos] + 1;
                continue;
            }

            v[pos] = C[i];
            p[pos] = currentRoot;
            p[currentRoot] = min(p[currentRoot], -pos);

            pos++;
        }

        //for(int i=1; i<n; i++) cout<<v[i]<<" "; cout<<"\n";
        //for(int i=1; i<n; i++) cout<<p[i]<<" "; cout<<"\n\n";
    }

    for(int i=1; i<n; i++) g<<v[i]<<"\n";

    return 0;
}