Cod sursa(job #1205339)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 6 iulie 2014 02:02:13
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<fstream>
#include<bitset>
#include<cstdlib>
using namespace std;

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

const int NMAX=1000005;

int n;
int a[NMAX],b[NMAX],c[NMAX],v[NMAX];
bitset<NMAX>viz;
int aint[4*NMAX];

inline int CreareAint(int nod,int st,int dr)
{
    if (st==dr)
        {
            aint[nod]=viz[st];
            return aint[nod];
        }
    else
        {
            int mij;
            mij=(st+dr)>>1;
            aint[nod]=CreareAint(2*nod,st,mij)+CreareAint(2*nod+1,mij+1,dr);
            return aint[nod];
        }
}

inline int QuerySum(int nod,int st,int dr,int a,int b)
{
    if (a>b) return 0;
    if (st>=a && dr<=b) return aint[nod];
    else
        {
            int mij=(st+dr)>>1,rez=0;
            if (a<=mij) rez+=QuerySum(2*nod,st,mij,a,b);
            if (b>mij) rez+=QuerySum(2*nod+1,mij+1,dr,a,b);
            return rez;
        }
}

inline void QueryPoz(int nod,int st,int dr,int s,int &self)
{
    if (st==dr) self=st;
    else
        {
            int mij=(st+dr)>>1;
            if (aint[2*nod]<s) QueryPoz(2*nod+1,mij+1,dr,s-aint[2*nod],self);
            else QueryPoz(2*nod,st,mij,s,self);
        }
}

inline int Update(int nod,int st,int dr,int loc)
{
    if (st==dr)
        {
            aint[nod]=0;
            return aint[nod];
        }
    else
        {
            int mij=(st+dr)>>1;
            if (loc<=mij) Update(2*nod,st,mij,loc);
            if (loc>mij) Update(2*nod+1,mij+1,dr,loc);
            aint[nod]=aint[2*nod]+aint[2*nod+1];
            return aint[nod];
        }
}

int main()
{
    int i,j,loc,nr;
    fin>>n>>a[1]>>b[1]>>c[1];
    for (i=1;i<=n-1;i++) viz[i]=1;
    CreareAint(1,1,n-1);
    for (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;
        }
    for (i=n-1;i>=1;i--)
        {
            if (a[i]>b[i]) swap(a[i],b[i]);
            nr=QuerySum(1,1,n-1,a[i],b[i]);
            for (j=1;j<=nr;j++)
                {
                    QueryPoz(1,1,n-1,j+QuerySum(1,1,n-1,1,a[i]-1),loc);
                    v[loc]=c[i];
                    viz[loc]=0;
                    Update(1,1,n-1,loc);
                }
        }
    for (i=1;i<=n-1;i++) fout<<v[i]<<"\n";
    return 0;
}