Cod sursa(job #2290311)

Utilizator Digori04Digori Parascovia Digori04 Data 26 noiembrie 2018 11:46:23
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
 
int aib[30010],n,sol,logn;
 
void update(int x,int val)
{
    for(int i=x; i<=n; i+=i&(-i))
    {
        aib[i]+=val;
    }
}
 
int query(int x)
{
    int ret=0;
 
    for(int i=x; i>0; i-=i&(-i))
    {
        ret+=aib[i];
    }
    return ret;
}
 
int search(int nr)
{
    int poz = 0;
    for(int i=logn;i>=0;--i)
    {
        if((poz+(1<<i))<=n&&aib[poz+(1<<i)]<nr)
        {
            poz+=1<<i;
            nr-=aib[poz];
        }
    }
    return poz+1;
}
 
int main()
{
   
    fin>>n;
    int k=2, pos;
    for(int i=1; i<=n; i++) update(i,1);
    for(logn=1; (1<<logn)<=n; logn++);
    logn--;
    for(int j=2; j<=n; j++)
    {
        pos=search(k);
        update(pos,-1);
      	fout<<pos<<" ";
        k=(k-1+j)%(n-j+1);
        if(k==0) k=n-j+1;
    }
    pos=search(k);
   fout<<pos<<" ";
    return 0;
}