Cod sursa(job #529283)

Utilizator ooctavTuchila Octavian ooctav Data 4 februarie 2011 17:19:21
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.07 kb
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"order.in"};
const char OUT[] = {"order.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 30005;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b) 	for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b) 	for(int i = a ; i >= b ; i--)
#define FORIT(it, V) 	for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a + 

int N, POZ = 1;
int X, Y, CX;
int Arb[8 * NMAX];

int mod(int a, int b)
{
	return (a - 1) % b + 1;
}

void update(int st, int dr, int nod)
{
	if(st == dr)
	{
		Arb[nod] = Y;
		return;
	}
	int mij = (st + dr) / 2;
	if(X <= mij)	update(st, mij, 2 * nod);
	else			update(mij + 1, dr, 2 * nod + 1);
	Arb[nod] = Arb[2 * nod] + Arb[2 * nod + 1];
}

int query(int st, int dr, int nod)
{
	if(X <= st && dr <= Y)
		return Arb[nod];
	int mij = (st + dr) / 2, rez = 0;
	if(X <= mij)	rez += query(st, mij, 2 * nod);
	if(mij + 1 <= Y)rez += query(mij + 1, dr, 2 * nod + 1);
	return rez;
}

int elem(int st, int dr, int nod)
{
	if(st == dr)
		return st;
	int mij = (st + dr) / 2;
	if(Arb[2 * nod] >= X)
		return elem(st, mij, 2 * nod);
	else
	{
		X -= Arb[2 * nod];
		return elem(mij + 1, dr, 2 * nod + 1);
	}
}

void rezolva()
{
	FOR(i, 1, N)
	{
		X = i; Y = 1;
		update(1, N, 1);
	}
	FOR(i, 1, N)
	{
		X = POZ + 1; Y = N;
		int k = query(1, N, 1);
		if(i <= k)
		{
			int l = N - (i - 1) - k;
			X = l + i;
			printf("%d ", CX = elem(1, N, 1));
		}
		else
		{
			X = mod(i - k, N - (i - 1));
			printf("%d ", CX = elem(1, N, 1));
		}
		X = CX; Y = 0;
		update(1, N, 1);
		POZ = CX;
	}
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	scanf("%d", &N);
	rezolva();
	return 0;
}