Cod sursa(job #742859)

Utilizator ioanabIoana Bica ioanab Data 1 mai 2012 21:05:28
Problema Order Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>
using namespace std;

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

const int N=30005;

int aib[N];
int n;

int step(int x)
{
    return x&(-x);
}

int query(int x)
{
    int sum=0;

    for(;x;x-=step(x))
        sum+=aib[x];

    return sum;
}

void update(int x,int val)
{
    for(;x<=n;x+=step(x))
        aib[x]+=val;
}

int bs(int val)
{
    int i,pas=1<<16;

    for(i=0;pas;pas>>=1)
        if(i+pas<=n && aib[i+pas]<val)
        {
            i+=pas;
            val-=aib[i];
        }
    return i+1;
}


int main()
{
	int i,nr=1,q;
	in>>n;   
	
	for(i=1;i<=n;i++)
		update(i,1);
	
	for(i=1;i<=n-1;i++)
	{
		q=bs((query(nr)+i)%(query(n)));
		out<<q<<" ";
		update(q,-1);
		nr=q;
	}
	out<<bs(1)<<"\n";
		
    return 0;
}