Cod sursa(job #2729700)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 25 martie 2021 09:42:14
Problema Order Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream f("order.in");
ofstream g("order.out");

int t[120001];
int N;

void build(int v, int tl, int tr){
	if(tl == tr)
		t[v] = 1;
	else{
		int tm = (tl + tr) >> 1;
		build(v << 1, tl, tm);
		build(v << 1 | 1, tm + 1, tr);
		t[v] = t[v << 1] + t[v << 1 | 1];
	}
}

int get_sum(int v, int tl, int tr, int l, int r){
	if(l > r)
		return 0;
	if(l == tl && r == tr){
		return t[v];
	}
	int tm = (tl + tr) >> 1;
	return get_sum(v << 1, tl, tm, l, min(r, tm)) + get_sum(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r);
}

int find_kth(int v, int tl, int tr, int k){
	if(k > t[v])
		return -1;
	if(tl == tr)
		return tl;
	int tm = (tl + tr) >> 1;
	if(t[v << 1] >= k)
		return find_kth(v << 1, tl, tm, k);
	else
		return find_kth(v << 1 | 1, tm + 1, tr, k - t[v << 1]);
}

void update(int v, int tl, int tr, int pos, int new_val){
	if(tl == tr){
		t[v] = new_val;
	} else{
		int tm = (tl + tr) >> 1;
		if(pos <= tm)
			update(v << 1, tl, tm, pos, new_val);
		else
			update(v << 1 | 1, tm + 1, tr, pos, new_val);
		t[v] = t[v << 1] + t[v << 1 | 1];
	}
}



int main(){
	f >> N;
	build(1, 1, N);

	int poz = 1;
	for(int i = 1;i <= N;i++){
		int k = (get_sum(1, 1, N, 1, poz) + i) % (N - i + 1);
		if(!k) k = (N - i + 1);
		poz = find_kth(1, 1, N, k);
		g << poz << " ";
		update(1, 1, N, poz, 0);

	}
}