Cod sursa(job #1660334)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 22 martie 2016 23:27:21
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <cstring>

using namespace std;

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

class Aib {

private:

	int dim;
	vector<int> aib;

	inline int lsb(int x) {
		return (x & (-x));
	}

public:

	Aib(int dim) {

		this->dim = dim;
		aib.resize(dim + 5, 0);

	}

	void update(int pos, int val) {

		for (int i = pos; i <= dim; i += lsb(i))
			aib[i] += val;

	}

	int query1(int pos) {

		int ans = 0;
		for (int i = pos; i; i -= lsb(i))
			ans += aib[i];

		return ans;

	}

	int query2(int val) {

		int sum = 0, step = 1;
		while (step < dim)
			step <<= 1;

		int i;
		for (i = 0; step; step >>= 1) {

			if (i + step > dim)
				continue;

			if (sum + aib[i + step] < val) {
				sum += aib[i + step];
				i += step;
			}

		}

		if (i < dim && query1(i + 1) == val)
			return i + 1;
		else
			return -1;

	}

} *aib;

int main() {

	int n;
	fin >> n;

	aib = new Aib(n);

	for (int i = 1; i <= n; ++i)
		aib->update(i, 1);

	int curr = 1;
	for (int i = 1; i <= n; ++i) {

		curr = (curr + i) % (n - i + 1);

		if (curr == 0)
			curr = n - i + 1;

		int pos = aib->query2(curr);
		
		fout << pos << ' ';

		--curr;

		aib->update(pos, -1);

	}

	fout << '\n';

	return 0;

}

//Trust me, I'm the Doctor!