Cod sursa(job #486456)

Utilizator andra23Laura Draghici andra23 Data 21 septembrie 2010 18:17:52
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<fstream>
#include<iostream>
#define maxn 1000005

using namespace std;

int r[maxn], cul[maxn], t[maxn];

int find(int x){
    int rad = x, y;
    while (rad != t[rad])
        rad = t[rad];
    while (x != t[x]){
        y = t[x];
        t[x] = rad;
        x = y;    
    } 
    return rad;   
}

int main(){
    ifstream f("curcubeu.in");
    ofstream g("curcubeu.out");
    int n, a, b, c, x, aux, a1, b1, c1;
    f>>n>>a>>b>>c;
    long long rez, m;
    int i, j, k;
    
    r[1] = 1;
    for (i = 2; i <= n-1; i++){
        m = (long long)r[i-1];
        rez = m*i;
        r[i] = rez%n;
    }
    
    for (i = n-1; i >= 1; i--){
        a1 = ((long long)a*r[i])%n; 
        b1 = ((long long)b*r[i])%n;
        c1 = ((long long)c*r[i])%n;  
        if (a1 > b1){
            aux = a1;
            a1 = b1;
            b1 = aux;
        }
        if (t[b1] == 0){
            t[b1] = b1;
            cul[b1] = c1;
        }
        else 
            b1 = find(b1);
        x = a1;
        while (x < b1){
            if (t[x] == 0){
                cul[x] = c1;
                t[x] = b1;    
            }    
            else 
                x = find(x);
            x++;
        }
    }
    
    for (i = 1; i <= n-1; i++)
        g<<cul[i]<<'\n';    
    
    return 0;
}