Cod sursa(job #2047824)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 25 octombrie 2017 13:45:17
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include <fstream>

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