Cod sursa(job #2088008)

Utilizator sandupetrascoPetrasco Sandu sandupetrasco Data 14 decembrie 2017 17:46:53
Problema Schi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.15 kb
#include <bits/stdc++.h>

#define pb push_back 
#define x first 
#define y second 
#define MOD 1000000007
#define z(x) (x & (-x))

using namespace std;
typedef long long ll;
typedef pair< int , int > PII;
const int dirx[] = {-2,-1,1,2, 1, -1};
const int diry[] = {0,1,1,0, -1, -1};
inline void debugMode() {
    #ifndef ONLINE_JUDGE
    freopen("schi.in", "r", stdin);
    freopen("schi.out", "w", stdout);
    #endif
}

int AIB[30100], n, x, a[30100];
int RS[30100];

void update(int x, int val){
	for (int i = x; i <= n; i += z(i))
		AIB[i] += val;
}

int get(int x){
	int rs = 0;
	for (int i = x; i; i -= z(i))
		rs += AIB[i];
	return rs;
}

int main(){
	debugMode();
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		update(i, 1);
	}
	
	for (int i = n; i; i--){
		int st = 1, dr = n, rsp;
		while (st <= dr){
			int mid = (st + dr) >> 1;
			int rs = get(mid);
			if (rs == a[i] && !RS[mid]){rsp = mid; break;}
			else if (rs > a[i] || (rs == a[i] && RS[mid])) dr = mid - 1;
			else st = mid + 1;
		}
		RS[rsp] = i;
		update(rsp, -1);
		
	}

	for (int i = 1; i <= n; i++) cout << RS[i] << '\n';
	
	return 0;
}