Cod sursa(job #2729703)

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

int t[120001];
int N, q;

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

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 << " ";
	}
}