Cod sursa(job #2030412)

Utilizator refugiatBoni Daniel Stefan refugiat Data 1 octombrie 2017 16:37:38
Problema Curcubeu Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.02 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream si("curcubeu.in");
ofstream so("curcubeu.out");
int a[1000005],b[1000005],c[1000005],v[1000005],nxt[1000005];

int fnd(int x)
{
    int r=x,r1;
    while(x!=nxt[x])
        x=nxt[x];
    while(r!=x)
    {
        r1=nxt[r];
        nxt[r]=x;
        r=r1;
    }
    return x;
}
int main()
{
    int n;
    si>>n>>a[1]>>b[1]>>c[1];
    for(int i=1;i<=n;++i)
        nxt[i]=i;
    for(int i=2;i<n;++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;
    }
    int a1,b1,c1;
    for(int i=n-1;i>0;--i)
    {
        if(a[i]>b[i])
            swap(a[i],b[i]);
        a1=a[i];
        b1=b[i];
        c1=c[i];
        while(a1<=b1)
        {
            a1=fnd(a1);
            if(a1<=b1)
            {
                v[a1]=c1;
                nxt[a1]=b1+1;
                a1++;
            }
        }
    }
    for(int i=1;i<n;++i)
        so<<v[i]<<'\n';
    return 0;
}