Cod sursa(job #825380)

Utilizator deneoAdrian Craciun deneo Data 29 noiembrie 2012 01:40:41
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <iostream>
using namespace std;

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

#define MAXN 1 << 15

int N, arb[MAXN];

void update (int poz, int val) {
	while (poz <= N) {
		arb[poz] += val;
		poz += poz & (-poz);
	}
}

int search (int val) {
	int lastrez = 0, rez, pas = 1 << 15;
	
	for (rez = 0; pas; pas >>= 1) {
		if (rez + pas <= N) {
			if (val > arb[rez + pas]) {
				rez += pas;
				val -= arb[rez];
				
			}
			if(val == arb[rez + pas])
				lastrez = rez + pas;
		}
	}
	return lastrez;
}

int main () {
	fin >> N;
	
	for (int i = 1; i <= N; ++i)
		update (i, 1);
	
	int pas = 2;
	for (int i = 0; i < N; ++i) {
		pas = (pas + i - 1) % (N - i) + 1;
		fout << search(pas) << " ";
		update (search(pas), -1);
	}
	return 0;
}