Cod sursa(job #950568)

Utilizator tudorv96Tudor Varan tudorv96 Data 17 mai 2013 10:26:22
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
using namespace std;

#define in "order.in"
#define out "order.out"
#define N 30005

int aib[N], n;

void add (int i, int x) {
	while (i <= n) {
		aib[i] += x;
		i += (i^(i-1)) & i;
	}
}

int query (int i) {
	int sum = 0;
	while (i) {
		sum += aib[i];
		i -= (i^(i-1)) & i;
	}
	return sum;
}

int BS (int x) {
	int lo = 1, hi = n + 1, sol = 0;
	while (lo < hi) {
		int mid = (lo + hi) >> 1, tmp = query(mid);
		if (tmp == x)
			sol = mid;
		if (tmp >= x)
			hi = mid;
		else
			lo = mid + 1;
	}
	return sol;
}

int main () {
	ifstream fin (in);
	fin >> n;
	fin.close();
	for (int i = 1; i <= n; ++i)
		add (i, 1);
	ofstream fout (out);
	int c = 1, done = n;	
	for (int pas = 1; pas <= n; ++pas) {
		c += pas;
		c = (c - 1) % done + 1;
		int mod = BS (c);
		fout << mod << " ";
		add (mod, -1);
		c--;
		done--;
	}
	fout.close();		
	return 0;
}