Cod sursa(job #2754434)

Utilizator HadircaDionisieHadirca Dionisie HadircaDionisie Data 25 mai 2021 20:12:44
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int n, tree[120020], xs[30005];



void build(int nod, int lo, int hi) {
	if (lo == hi) {
		tree[nod] = 1;
		return;
	}
	int mid = (lo + hi) / 2;
	build(nod * 2, lo, mid);
	build(nod * 2 + 1, mid + 1, hi);
	tree[nod] = tree[nod * 2] + tree[nod * 2 + 1];
}

void update(int nod, int lo, int hi, int poz, int val) {
	if (poz == lo && poz == hi) {
		tree[nod] = val;
		return;
	}
	int mid = (lo + hi) / 2;
	if (poz <= mid) {
		update(nod * 2, lo, mid, poz, val);
	}
	else {
		update(nod * 2 + 1, mid + 1, hi, poz, val);
	}
	tree[nod] = tree[nod * 2] + tree[nod * 2 + 1];
}

int rez;

void query(int nod, int lo, int hi,int s) {
	if (lo == hi) {
		rez = lo;
		return;
	}
	int mid = (lo + hi) / 2;
	if (s <= tree[nod * 2]) {
		query(nod * 2, lo, mid, s);
	}
	else {
		query(nod * 2 + 1, mid + 1, hi, s-tree[nod*2]);
	}

}



int main() {

	fin >> n;
	build(1, 1, n);

	int nr = n;
	int cnt = 1;

	for (int i = 1; i <= n; i++) {
		cnt += i;
		cnt %= nr;
		if (cnt == 0) {
			cnt = nr;
		}
		query(1, 1, n, cnt);
		fout << rez << ' ';
		update(1, 1, n, rez, 0);

		nr -= 1;
		cnt -= 1;
	}

	return 0;
}