Cod sursa(job #1099510)

Utilizator Al3ks1002Alex Cociorva Al3ks1002 Data 5 februarie 2014 21:35:17
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<cstdio>
using namespace std;
const int NMAX = 30005;
int N,i,poz,len,aib[NMAX],l,r,m,sol,Q;
void Update(int poz,int val)
{
    for(int i=poz;i<=N;i+=i&(-i)) aib[i]+=val;
}
int Query(int poz)
{
    int ans=0;
    for(int i=poz;i;i-=i&(-i)) ans+=aib[i];
    return ans;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i<=N;i++) Update(i,1);
    for(i=1,poz=2;i<=N;i++)
    {
        len=N-i+1;
        poz=(poz+i-1)%len;
        if(!poz) poz=len;
        l=1; r=N;
        while(l<=r)
        {
            m=(l+r)/2; Q=Query(m);
            if(Q<poz) l=m+1;
            else if(Q>poz) r=m-1;
            else {sol=m; r=m-1;}
        }
        printf("%d ",sol);
        Update(sol,-1);
    }
    return 0;
}