Cod sursa(job #2646606)

Utilizator saeed_odakSaeed Odak saeed_odak Data 1 septembrie 2020 16:02:18
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
// Oh damn, cann't you see I'm fine?

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

struct FenwickTree {

	int n;
	vector <int> t;

	FenwickTree(int nn) {
		n = nn;
		t.resize(n + 1);
	}

	void update(int idx, int delta) {
		while(idx <= n) {
			t[idx] += delta;
			idx += (idx & -idx);
		}
	}

	int sum(int idx) {
		int res = 0;
		while(idx > 0) {
			res += t[idx];
			idx -= (idx & -idx);
		}
		return res;
	}

	// largest index such that sum[idx] < val (or last)
	int firstIndexOfGE(int val) {
		int step = (1 << 30);
		int i = 0;
		int now = 0;
		while (step > 0) {
			if (i + step <= n && now + t[i + step] < val) {
				now += t[i + step];
				i += step;
			}
			step /= 2;
		}
		return i;
	}

	void debug() {
		for(int i = 1; i <= n; i++) {
			cerr << sum(i) - sum(i - 1) << " ";
		}
		cerr << endl;
	}

};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	freopen("order.in", "r", stdin);
	freopen("order.out", "w", stdout);

	int n;
	cin >> n;
	FenwickTree ft(n);
	for(int i=1; i<=n; i++) ft.update(i, 1);
	int now = 1;
	int all = n;
	for(int i=1; i<=n; i++) {
		int j = i % all;
		if(j == 0) j = all;
		int rem = ft.sum(n) - ft.sum(now);
		if(rem < j) {
			now = 0;
			j -= rem;
		}
		int l = now, r = n, m;
		while(r > l) {
			m = (l + r) >> 1;
			int v = ft.sum(m) - ft.sum(now);
			if(v > j) r = m-1;
			else if(v < j) l = m+1;
			else r = m;
		}
		cout << r << " ";
		ft.update(r, -1);
		now = r;
		all--;
	}

	return 0;
}