Cod sursa(job #679163)

Utilizator balakraz94abcd efgh balakraz94 Data 12 februarie 2012 20:28:38
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <cstdio>
#include <algorithm>
#define infile "schi.in"
#define outfile "schi.out"
#define n_max 30005
using namespace std;


int AI[3*n_max];

int a[n_max], Sol[n_max];

int N;


void citeste()
{
	freopen(infile, "r", stdin);
	
	scanf("%d",&N);
	
	for(int i=1; i<=N; ++i)
		scanf("%d",&a[i]);
	
	fclose(stdin);
}



void build(int nod, int st, int dr)
{
	AI[nod] = dr - st + 1;
	
	if(st == dr)
		return;
	
	int mij = st + (dr - st)/2;
	
	build(2*nod, st, mij);
	build(2*nod+1, mij+1, dr);	
}


int query(int nod, int st, int dr, int val)
{
	if(st == dr)
		return st;
	
	int mij = st + (dr - st)/2;
	
	if(val <= AI[2*nod])
		return query(2*nod, st, mij, val);
	return query(2*nod+1, mij+1, dr, val - AI[2*nod]);	
}



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



void rezolva()
{
	build(1, 1, N);
	
	for(int i=N; i; --i)
	{
		int poz = query(1, 1, N, a[i]);
		
		Sol[poz] = i;
		
		update(1, 1, N, poz);
	}
}



void afiseaza()
{
	freopen(outfile, "w", stdout);
	
	for(int i=1; i<=N; ++i)
		printf("%d\n",Sol[i]);
	
	fclose(stdout);
}



int main(void)
{
  
    citeste();
	rezolva();
	afiseaza();
    
    return 0;
}