Cod sursa(job #3189770)

Utilizator emazareMazare Emanuel emazare Data 6 ianuarie 2024 14:49:31
Problema Curcubeu Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>

using namespace std;

ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");

const int Nmax = 1000005;
long long father[Nmax],a[Nmax],b[Nmax],c[Nmax],sol[Nmax];

long long find_root(long long x){
    if(father[x]<0)
        return x;
    long long root = find_root(father[x]);
    father[x] = root;
    return root;
}
void unite(long long x, long long y){
    long long rx = find_root(x);
    long long ry = find_root(y);
    if(rx == ry)
        return;
    if(rx>ry)
        swap(rx,ry);
    father[ry]+=father[rx];
    father[rx] = ry;
}

int main()
{
    long long n,i,j;
    fin >> n >> a[1] >> b[1] >> c[1];
    father[1] = -1;
    for(i=2;i<n;i++){
        father[i] = -1;
        a[i] = (a[i-1]*i)%n;
        b[i] = (b[i-1]*i)%n;
        c[i] = (c[i-1]*i)%n;
        if(a[i]>b[i])
            swap(a[i],b[i]);
    }
    for(i=n-1;i>0;i--){
        j = a[i];
        while(j<=b[i]){
            if(sol[j]>0)
                j = find_root(j)+1;
            else{
                if(sol[j-1]>0)
                    unite(j-1,j);
                if(sol[j+1]>0)
                    unite(j,j+1);
                sol[j] = c[i];
                j++;
            }
        }
    }
    for(i=1;i<n;i++)
        fout << sol[i] << '\n';
    return 0;
}