Cod sursa(job #2400520)

Utilizator onipreponiprep oniprep Data 8 aprilie 2019 20:28:07
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
const int N=30009;
int n;
int v[N],aib[N];
void update(int x,int y)
{
    while(x<=n)
    {
        aib[x]+=y;
        x+=x&(-x);
    }
}
int query(int x)
{
    int sum=0;
    while(x)
    {
        sum+=aib[x];
        x-=x&(-x);
    }
    return sum;
}
int bin(int st,int dr,int val)
{
    int sol=-1;
    while(st<=dr)
    {
        int mij=(st+dr)/2,ans=query(mij);
        if(ans==val)
            sol=mij;
        if(ans>=val)
            dr=mij-1;
        else
            st=mij+1;
    }
    return sol;
}
void read()
{
    fin>>n;
}
void solve()
{
    for(int i=1;i<=n;i++)
        update(i,1);
    int ans=0,pas=0,nn=n,pasr=0;
    int curr=1;
    while(nn)
    {
        pas++;
        int next=query(curr)+pas;
        next%=nn;
        if(next==0)
            next+=nn;
        ans=bin(1,n,next);
        update(ans,-1);
        curr=ans;
        fout<<ans<<" ";
        nn--;
    }
}
int main()
{
    read();
    solve();
    return 0;
}