Cod sursa(job #830274)

Utilizator toranagahVlad Badelita toranagah Data 6 decembrie 2012 16:23:22
Problema Order Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <iostream>
using namespace std;
const int MAX_N = 1 << 15;
ifstream fin("order.in");
ofstream fout("order.out");
int aib[MAX_N + 1];
int N;
void update(int , int);
int search(int);
int main() {
	fin >> N;
	for (int i = 1; i <= N; ++i) update(i, 1);
		int step = 2; 
	for (int i = 0; i < N; ++i) {
		step = (step + i - 1) % (N - i) + 1;
        cerr << step << endl;
		int cut = search(step);
		fout << cut << ' ';
		update(cut, -1);
	}
	return 0;
}

void update(int pos, int val) {
	for (int i = pos; i <= N; i += (i & -i)) {
		aib[i] += val; 
	}
}

int search(int val) {
	int result = 0, x = 0;
	for (int i = MAX_N; i; i /= 2) {
        if (x + i <= N) {
			if (aib[x + i] < val) {
				x += i;
				val -= aib[x];
			}
			if (val == aib[x + i]) {
				result = i + x;
			}
		}
	}
	return result;
}