Cod sursa(job #1022528)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 5 noiembrie 2013 17:34:09
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
using namespace std;

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

#define NMAX 30001
#define L (node << 1)
#define R (L | 1)

int i, j, n, N, K;

int H[3 * NMAX];

void update(int node, int left, int right, int poz, int val) {
	if (left == right){H[node] = val; return;}
	int mid = (left + right) >> 1;
	if (poz <= mid) 
		update(L, left, mid, poz, val);
	else
		update(R, mid + 1, right, poz, val);
	H[node] = H[L] + H[R];
}

void query(int node, int left, int right, int k) {
	if (left == right) {
		K = left;
		return;
	}
	int mid = (left + right) >> 1;
	if (H[L] >= k)
		query(L, left, mid, k);
	else
		query(R, mid + 1, right, k - H[L]);
}

void build(int node, int left, int right) {
	if (left == right){H[node] = 1; return;}
	int mid = (left + right) >> 1;
	build(L, left, mid);
	build(R, mid + 1, right);
	H[node] = H[L] + H[R];
}

int main() {
	fin >> N;
	n = N;
	i = j = 1;
	build(1, 1, n);
	while (N) {
		j += i;
		j %= N;
		if (i != 1) --j;
		if (j == -1) j = N - 1;
		if (j == 0) j = N;
		query(1, 1, n, j);
		update(1, 1, n, K, 0);
		fout << K << ' ';
		++i;
		--N;
	}
	fout << '\n';
	return 0;
}