Cod sursa(job #161553)

Utilizator scvalexAlexandru Scvortov scvalex Data 18 martie 2008 14:56:35
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <iostream>
#include <fstream>

using namespace std;

int N;
int arb[30001*4];
int v[30001],
	R[30001];
int L;

void printt() {
	for (int i(1); i <= 4*N; ++i)
		cout << arb[i] << " ";
	cout << endl;
}

void update(int nod, int pos, int val, int left, int right) {
	if (left == right) {
		arb[nod] = val;
		return;
	}

	int middle = (left + right)/ 2;
	if (pos < middle)
		update(nod * 2, pos, val, left, middle);
	else
		update(nod * 2 + 1, pos, val, middle + 1, right);

	arb[nod] = arb[2*nod] + arb[2*nod+1];
}

void cut(int nod, int pos, int left, int right) {
//	cout << nod << " " << pos << " " << left << " " << right << endl;
	if (left == right) {
		L = left;
		arb[nod] = 0;
		return;
	}

	int middle = (left + right) / 2;
	if (arb[nod*2] < pos)
		cut(nod*2+1, pos - arb[nod*2], middle+1, right);
	else
		cut(nod*2, pos, left, middle);

	arb[nod] = arb[2*nod] + arb[2*nod+1];
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("schi.in", "r");
	fscanf(fi, "%d", &N);
	for (int i(0); i < N; ++i)
		fscanf(fi, "%d", v + i);
	fclose(fi);

	/*for (int i(0); i < N; ++i)
		printf("%d ", v[i]);
	printf("\n");*/

	for (int i(0); i < N; ++i) {
		update(1, i, 1, 1, N);
		//printt();
	}

	for (int i = N - 1; i >= 0; --i) {
		//printt();
		cut(1, v[i], 1, N);
		//cout << L << endl;
		R[L - 1] = i + 1;
	}

	FILE *fo = fopen("schi.out", "w");
	for (int i(0); i < N; ++i)
		fprintf(fo, "%d\n", R[i]);
	fclose(fo);

	return 0;
}