Cod sursa(job #529358)

Utilizator ooctavTuchila Octavian ooctav Data 4 februarie 2011 19:34:01
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 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[] = {"schi.in"};
const char OUT[] = {"schi.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 sol[NMAX];
int scot[NMAX];

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

void citi()
{
	scanf("%d", &N);
	FOR(i, 1, N)	scanf("%d", &scot[i]);
}

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);
	}
	IFOR(i, N, 1)
	{
		X = scot[i];
		CX = elem(1, N, 1);
		sol[CX] = i;
		X = CX;Y = 0;
		update(1, N, 1);
	}
}

void scrie()
{
	FOR(i, 1, N)	printf("%d\n", sol[i]);
}

int main()
{
	freopen(IN, "r", stdin);
	freopen(OUT, "w", stdout);
	citi();
	rezolva();
	scrie();
	return 0;
}