Cod sursa(job #2045943)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 23 octombrie 2017 09:36:03
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <fstream>

using namespace std;
ifstream f("order.in");
ofstream g("order.out");
int aint[120000],a,pos,n,m,i;
void update(int st,int dr,int nod)
{
    if(st==dr)
    {
        aint[nod]=a;
    }
    else
    {
        int mij=(st+dr)/2;
        update(st,mij,nod*2);
        update(mij+1,dr,nod*2+1);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}
void update2(int st,int dr,int pos,int nod)
{
    int mij=(st+dr)/2;
    if(st==dr)
    {
        aint[nod]=0;
    }
    else if(mij>=pos)
    {
        update2(st,mij,pos,2*nod);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
    else
    {
        update2(mij+1,dr,pos,2*nod+1);
        aint[nod]=aint[2*nod]+aint[2*nod+1];
    }
}
int query(int st,int dr,int p1,int nod)
{
    int mij=(st+dr)/2;
    if(st==dr)
    {
        update2(1,n,pos,1);
        return st;
    }
    if(aint[2*nod]<p1)
    {
        return query(mij+1,dr,p1-aint[2*nod],2*nod+1);
    }
    else
    {
        return query(st,mij,p1,2*nod);
    }
}
int main()
{
    f>>n;
    m=n;
    a=1;
    update(1,n,1);
    pos=1;
    for(i=1; i<=n; i++)
    {
        if(i+pos>=n)
        {
            pos=(i+pos)%m;
            if(pos==0)
            {
                pos=m;
            }
        }
        else
        {
            pos=i+pos;
        }
        g<<query(1,n,pos,1)<<" ";
        m--;
    }
    return 0;
}