Cod sursa(job #2047991)

Utilizator MoleRatFuia Mihai MoleRat Data 25 octombrie 2017 18:01:52
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("curcubeu.in");
ofstream fout("curcubeu.out");
int A[10000010],B[10000010],C[10000010];
int rez[10000010],par[10000010];
int findRoot(int x)
{
    if (x!=par[x])
        par[x]=findRoot(par[x]);
    return par[x];
}
void makeSet(int p)
{
    par[p]=p;
}
int main()
{
    int n;
    fin>>n>>A[1]>>B[1]>>C[1];
    makeSet(1);
    for(int i=2; i<=n-1; i++)
    {
        A[i]=(1LL*A[i-1]*i)%n;
        B[i]=(1LL*B[i-1]*i)%n;
        C[i]=(1LL*C[i-1]*i)%n;
        makeSet(i);
    }
    makeSet(n);
    for(int i=n-1; i>=1; i--)
    {
        int st=A[i],dr=B[i];
        if(A[i]>B[i])
        {
            st=B[i];
            dr=A[i];
        }

        st=findRoot(st);
        while(st<=dr)
        {
            rez[st]=C[i];
            par[st]=dr+1;
            st=findRoot(st+1);
        }
    }
    for(int i=1; i<=n-1; i++)
    {
        fout<<rez[i]<<"\n";
    }

    return 0;
}