Cod sursa(job #2000834)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 14 iulie 2017 20:51:15
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
using namespace std;
const int nmax=30004;
int aib[nmax],vs[nmax];
int n,pos=2;
void update(int pos,int val)
{
    for(;pos<=n;pos+=(pos&(pos^(pos-1)))) aib[pos]+=val;
}
int query(int pos)
{
    int sum=0;
    for(;pos>0;pos-=(pos&(pos^(pos-1)))) sum+=aib[pos];
    return sum;
}
int qry(int p1,int p2)
{
    return query(p2)-query(p1-1);
}
inline void define()
{
    printf("%d ",2);
    vs[2]=1;
    for(int i=1;i<=n;i++)
    {
        if(i==2) continue;
        update(i,1);
    }
}
inline void solve()
{
    for(int x=2;x<=n;x++)
    {
        int v=x,valt=qry(pos,n);
      //  printf("%d %d %d\n",query(n-1),query(n),valt);
        if(valt<v)
        {
            pos=1;
            v-=valt;
            valt=qry(1,n);
            v%=valt;
            if(v==0) v=valt;
        }
       // printf("%d %d\n",v,pos);
        int st=pos,dr=n,ans=0;
        while(st<=dr)
        {
            int mij=(st+dr)/2,valt=qry(pos,mij);
            if(valt>=v)
            {
                ans=mij;
                dr=mij-1;
            }
            else st=mij+1;
        }
       // while(vs[ans]==1) ++ans;
        vs[ans]=1;
        printf("%d ",ans);
        pos=ans;
        update(pos,-1);
    }
}
int main()
{
    freopen ("order.in","r",stdin);
    freopen ("order.out","w",stdout);
    scanf("%d",&n);
    define();
    solve();
}