Cod sursa(job #1477755)

Utilizator greenadexIulia Harasim greenadex Data 26 august 2015 21:06:11
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair

using namespace std;

const string name = "order",
             in_file = name + ".in",
             out_file = name + ".out";

ifstream fin(in_file);
ofstream fout(out_file);

const int MAX = 3e4 + 5;

int n, aib[MAX], viz[MAX], pmax = 1;

int lsb(int nr) {
	return nr & (-nr);
}

void update(int poz, int val) {
	for (int i = poz; i <= n; i += lsb(i))
		aib[i] += val;
}

int query(int nr) {
	int sol = 0;
	for (int p = pmax; p >= 1 && nr; p /= 2)
		if (sol + p <= n && aib[sol + p] <= nr) {
			nr -= aib[sol + p];
			sol += p;
		}

	while (viz[sol])
		sol--;
	return sol;
} 

int main() {
	fin >> n;
	
	while (pmax * 2 <= n) 
		pmax *= 2;
	for(int i = 1; i <= n; i++) 
		update(i, 1);

	for(int x = 2, ind, mod, i = 1; i <= n; i++) {
		mod = n - i + 1;
		x = (x + n - mod) % mod;
		if (!x)
			x = mod;
		ind = query(x);
		update(ind, -1);
		viz[ind] = 1;
		fout << ind << ' ';
	}
	return 0;
}