Cod sursa(job #2376981)

Utilizator tiberiu.bucur17Tiberiu Constantin Emanoil Bucur tiberiu.bucur17 Data 8 martie 2019 20:34:20
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <cstdio>
const int Maxn=30001;
int aint[4*Maxn],poz,salt;
int query(int nod,int st,int dr)
{
    if(poz<st)
        return aint[nod];
    int s=0,mid=(st+dr)>>1;
    if(poz<mid)
        s=query(2*nod,st,mid);
    return s+query(2*nod+1,mid+1,dr);
}
void dfs(int nod,int st,int dr)
{
    if(st==dr)
    {
        aint[nod]=1;
        return;
    }
    int mid=(st+dr)>>1;
    dfs(2*nod,st,mid);
    dfs(2*nod+1,mid+1,dr);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
}
void update(int nod,int st,int dr)
{
    aint[nod]--;
    if(st==dr)
    {
        poz=st;
        return;
    }
    int mid=(st+dr)>>1;
    if(salt<=aint[2*nod])
        update(2*nod,st,mid);
    else
    {
        salt-=aint[2*nod];
        update(2*nod+1,mid+1,dr);
    }
}
int main()
{
    FILE *fin,*fout;
    fin=fopen("order.in","r");
    fout=fopen("order.out","w");
    int n,dist;
    fscanf(fin,"%d",&n);
    dfs(1,1,n);
    poz=1;
    for(int i=1;i<n;i++)
    {
        dist=aint[1]-query(1,1,n);
        salt=i+dist;
        if(salt>aint[1])
            salt%=aint[1];
        update(1,1,n);
        fprintf(fout,"%d ",poz);
    }
    update(1,1,n);
    fprintf(fout,"%d",poz);
    fclose(fin);
    fclose(fout);
    return 0;
}