Cod sursa(job #955048)

Utilizator danalex97Dan H Alexandru danalex97 Data 30 mai 2013 19:57:29
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
using namespace std;

ifstream F("order.in");
ofstream G("order.out");

const int Nmax = 30010;

int AIB[Nmax],N;

int bit(int x)
{
    return ( x ^ (x-1) ) & x;
}

void add(int nod,int val)
{
    for (int i=nod;i<=N;i+=bit(i))
        AIB[i] += val;
}

int what(int nod)
{
    int val = 0;
    for (int i=nod;i;i-=bit(i))
        val += AIB[i];
    return val;
}

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

int main()
{
    F>>N;
    for (int i=1;i<=N;++i)
        add(i,1);
    for (int p=1,i=1;i<=N;++i)
    {
        p += i;
        p = p % (N-i+1) == 0 ? (N-i+1) : p % (N-i+1);
        int pl = bs(1,N,p);
        add(pl,-1);
        p = what(pl);
        G<<pl<<' ';
    }
    G<<'\n';
}