Cod sursa(job #1505289)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 18 octombrie 2015 23:33:09
Problema Schi Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#define maxN 30005*4

using namespace std;

int A[maxN],n;

struct vec{
	int poz, loc,ind;
} a[maxN];

void update(int l, int r, int i, int poz, int val){
	if (l == r){
		A[i] += val;
		return;
	}

	int m = (l + r) >> 1;
	if (m >= poz)
		update(l, m, i << 1, poz, val);
	else
		update(m + 1, r, (i << 1) + 1, poz, val);

	A[i] = A[i << 1] + A[(i << 1) + 1];
}

void cauta(int l, int r,int i, int x, int poz){
	if (x==1 && i!=1 && l == r){
		a[poz].loc = l;
		A[i] = 0;
		return;
	}

	int m = (l + r) >> 1;
	if (A[i << 1] < x)
		cauta(m+1,r,(i << 1) + 1, x - A[i << 1], poz);
	else
		cauta(l,m,i << 1, x, poz);

	A[i] = A[i << 1] + A[(i << 1) + 1];
}

bool cmp(vec x,vec y){
	return x.loc < y.loc;
}

int main(){
	ifstream f("schi.in");
	ofstream g("schi.out");

	f >> n;

	for (int i = 1; i <= n; ++i){
		f >> a[i].poz;
		a[i].ind = i;
		update(1, n, 1, i, 1);
	}

	for (int i = n; i >= 1; --i){
		cauta(1, n, 1, a[i].poz, i);
	}

	sort(a, a + n + 1, cmp);

	for (int i = 1; i <= n; ++i)
		g << a[i].ind << "\n";

	f.close();
	g.close();

	return 0;
}