Cod sursa(job #968461)

Utilizator VisuianMihaiMihai Visuian VisuianMihai Data 2 iulie 2013 09:29:42
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");

int n, aib[30001];
void Add(int x, int val)
{
    for(;x<=n; x+= x&-x)
        aib[x]+=val;
}
int Number(int x)
{
    int res=0;
    for(;x;x-= x&-x)
        res += aib[x];
    return res;
}

int bs(int st,int dr,int val)
{
    if ( st == dr )
        return st;
    int mid =(st+dr)/2;
    if ( Number(mid)>= val) return bs(st,mid,val);
    return bs(mid+1,dr,val);
}

int main()
{
    fin>>n;
    for(int i = 1; i<= n; i++ )
        Add(i,1);
    for(int i=1, p=1; i<= n; i++ )
    {
        p += i;
        if(p%(n-i+1)) p%=(n-i+1);
        else p = n-i+1;
        int res=bs(1,n,p);
        Add(res,-1);
        p=Number(res);
        fout<<res<<' ';
    }
    fin.close();
    fout.close();
    return 0;
}