Cod sursa(job #2154187)

Utilizator DenisacheDenis Ehorovici Denisache Data 6 martie 2018 19:20:34
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <bitset>
#include <set>

using namespace std;

int aint[30005 * 4];
int vec[30005];	

#define left_child (nod * 2)
#define right_child (left_child | 1)

void build_tree(int nod, int left, int right) {
	if (left == right) {
		aint[nod] = 1;
		return;
	}

	int mid = (left + right) / 2;
	
	build_tree(left_child, left, mid);
	build_tree(right_child, mid + 1, right);

	aint[nod] = aint[left_child] + aint[right_child];
}

int query_and_update_tree(int nod, int left, int right, int nr) {
	if (left == right) {
		aint[nod] = 0;
		return left;
	}

	int mid = (left + right) / 2;

	int pos = 0;

	if (nr <= aint[left_child]) pos = query_and_update_tree(left_child, left, mid, nr);
	else pos = query_and_update_tree(right_child, mid + 1, right, nr - aint[left_child]);

	aint[nod] = aint[left_child] + aint[right_child];

	return pos;
}

int main() {
	ios::sync_with_stdio(false);

	string filename = "order";

	ifstream fin(filename + ".in");
	ofstream fout(filename + ".out");

	int n;
	fin >> n;

	build_tree(1, 1, n);

	int ith_child = 1;
	int remaining_children = n;

	for (int i = 1; i <= n; ++i) {
		ith_child = (ith_child + i) % remaining_children;
		if (ith_child == 0) ith_child = remaining_children;
		--remaining_children;

		fout << query_and_update_tree(1, 1, n, ith_child) << " ";
		--ith_child;
	}

	//system("pause");
	return 0;
}