Cod sursa(job #1146417)

Utilizator a96tudorAvram Tudor a96tudor Data 18 martie 2014 22:38:14
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#define ub(x) (x&(-x))
using namespace std;
int AIB[30010],SOL,MOD,P,N,st,dr,mij,val;
inline int Qwerry(int p)
{
    int S=0;
    for (int i=p;i>0;i-=ub(i)) S+=AIB[i];
    return S;
}
inline void Update(int p,int val)
{
    for (int i=p;i<=N;i+=ub(i)) AIB[i]+=val;
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&N);
    for (int i=1;i<=N;++i) Update(i,1);
    for (int i=1,P=2;i<=N;++i)
    {
        MOD=N-i+1;
        P=(P+i-1)%MOD;
        if (!P) P=MOD;
        st=1; dr=N;
        while (st<=dr)
        {
            int mij=(st+dr)/2, val=Qwerry(mij);
            if(val<P) st=mij+1;
              else
              {
                 if(val>P) dr=mij-1;
                    else {
                            SOL=mij;
                            dr=mij-1;
                         }
             }
        }
        Update(SOL,-1);
        printf("%d ",SOL);
    }
    printf("\n");
    fclose(stdin); fclose(stdout);
    return 0;
}