Cod sursa(job #1814418)

Utilizator StefansebiStefan Sebastian Stefansebi Data 23 noiembrie 2016 22:40:40
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<fstream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");

int arb[100009];

void update(int n, int l, int r, int pos, int val) {
	if (l == r) {
		arb[n] = val;
		return;
	}
	int m = (l + r) / 2;
	if (pos <= m) {
		update(n * 2, l, m, pos, val);
	}
	else {
		update(n * 2 + 1, m + 1, r, pos, val);
	}
	arb[n] = arb[n * 2] + arb[n * 2 + 1];
}

void query(int n, int l, int r, int i, int& pos) {
	if (l == r) {
		pos = l;
		return;
	}
	int m = (l + r) / 2;
	if (i <= arb[n * 2]) {
		query(n * 2, l, m, i, pos);
	}
	else {
		query(n * 2 + 1, m + 1, r, i - arb[n * 2], pos);
	}
}

void query_int(int n, int l, int r, int lq, int rq, int& sum) {
	if (lq <= l && r <= rq) {
		sum = sum + arb[n];
		return;
	}
	int m = (l + r) / 2;
	if (lq <= m) {
		query_int(n * 2, l, m, lq, rq, sum);
	} 
	if (m < rq) {
		query_int(n * 2 + 1, m + 1, r, lq, rq, sum);
	}
}

int main() {
	int n;
	fin >> n;
	for (int i = 1; i <= n; i++) {
		update(1, 1, n, i, 1);
	}


	int pos = 1;
	for (int i = 1; i <= n; i++) {
		int current_pos = 0;
		//pe ce pozitie suntem in lista curenta
		query_int(1, 1, n, 1, pos, current_pos);//numarul cate pozitii valide sunt pana la pos
		current_pos += i; //facem pasii necesari
		current_pos %= arb[1];
		if (current_pos == 0) {
			current_pos = arb[1];
		} //pozitia pe lista noua de unde vom sterge

		int actual_pos = 0;
		query(1, 1, n, current_pos, actual_pos);
		fout << actual_pos << " ";
		update(1, 1, n, actual_pos, 0);
		pos = actual_pos;
	}
}