Cod sursa(job #1069175)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 29 decembrie 2013 15:52:07
Problema Schi Scor 100
Compilator cpp Status done
Runda qwertyu Marime 1.24 kb
#include <fstream>
using namespace std;

ifstream fin("schi.in");
ofstream fout("schi.out");

#define nmax 30001
#define L (node << 1)
#define R (L | 1)

int i, n, K;

int l[nmax], ans[nmax];
int H[nmax * 3];

void update(int node, int left, int right, int poz, int val) {
    if (left == right){H[node] = val; return;}
    int mid = (left + right) >> 1;
    if (poz <= mid) 
        update(L, left, mid, poz, val);
    else
        update(R, mid + 1, right, poz, val);
    H[node] = H[L] + H[R];
}
 
void query(int node, int left, int right, int k) {
    if (left == right) {
        K = left;
        return;
    }
    int mid = (left + right) >> 1;
    if (H[L] >= k)
        query(L, left, mid, k);
    else
        query(R, mid + 1, right, k - H[L]);
}

void build(int node, int left, int right) {
    if (left == right){H[node] = 1; return;}
    int mid = (left + right) >> 1;
    build(L, left, mid);
    build(R, mid + 1, right);
    H[node] = H[L] + H[R];
}

int main() {
	fin >> n;
	for (i = 1; i <= n; ++i) fin >> l[i];
	build(1, 1, n);
	for (i = n; i >= 1; --i) {
		query(1, 1, n, l[i]);
		ans[K] = i;
		update(1, 1, n, K, 0);
	}
	for (i = 1; i <= n; ++i) 
		fout << ans[i] << '\n';
	return 0;
}