Cod sursa(job #2080130)

Utilizator flibiaVisanu Cristian flibia Data 2 decembrie 2017 14:40:58
Problema Order Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
#define L 2 * pos
#define R 2 * pos + 1

using namespace std;

ifstream in("order.in");
ofstream out("order.out");

int n, h[120100], sol[30100], gg, wp, st, dr, mid, p, nr;		
	
void build(int st, int dr, int pos){
	if(st == dr){
		h[pos] = 1;
		return;
	}
	int mid = (st + dr) >> 1;
	build(st, mid, L);
	build(mid + 1, dr, R);
	h[pos] = h[L] + h[R];
}

void update(int st, int dr, int pos, int idx){
	if(st == dr){
		h[pos] = 0;
		return;
	}
	int mid = (st + dr) >> 1;
	if(idx <= mid)
		update(st, mid, L, idx);
	else
		update(mid + 1, dr, R, idx);
	h[pos] = h[L] + h[R];
}

int query(int st, int dr, int pos, int l, int r){
	if(l <= st && dr <= r)
		return h[pos];
	int mid = (st + dr) >> 1;
	int left = 0, right = 0;
	if(l <= mid)
		left = query(st, mid, L, l, r);
	if(r > mid)
		right = query(mid + 1, dr, R, l, r);
	return left + right;
}

void get(int st, int dr, int pos, int cur){
	if(st == dr){
		p = st;
		return;
	}
	int mid = (st + dr) >> 1;
	if(cur + h[L] >= nr)
		get(st, mid, L, cur);
	else
		get(mid + 1, dr, R, cur + h[L]);
}

int main(){
	in >> n;
	build(1, n, 1);
	p = 1;
	for(int i = 1; i <= n; i++){
		p = (p < n ? p + 1 : 1);
		wp = query(1, n, 1, p, n);
		gg = query(1, n, 1, 1, n);
		nr = i;
		st = 1, dr = n;
		while(st <= dr){
			mid = (st + dr) >> 1;
			if((mid - 1) * gg + wp <= nr)
				st = mid + 1;
			else 
				dr = mid - 1;
		}
		if(!dr){
			if(p > 1)
				gg = query(1, n, 1, 1, p - 1);
			nr += gg;
			get(1, n, 1, 0);
			update(1, n, 1, p);
			sol[i] = p;
		} else{
			nr -= wp;
			nr -= (dr - 1) * gg;
			if(!nr)
				nr += gg;
			get(1, n, 1, 0);
			update(1, n, 1, p);
			sol[i] = p; 
		}
	}
	for(int i = 1; i <= n; i++)
		out << sol[i] << ' ';
	return 0;
}