Cod sursa(job #1806357)

Utilizator alexsandulescuSandulescu Alexandru alexsandulescu Data 15 noiembrie 2016 10:38:19
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <fstream>
#include <climits>
#define ub(haha) (haha & (-haha))
using namespace std;

ifstream f ("order.in");
ofstream g ("order.out");

int N, poz, NX, x, AIB[30010];
void add(int poz, int val) {
	for(int i = poz; i <= N; i += ub(i)) AIB[i] += val;
}

int sum(int poz) {
	int SUM = 0;
	for(int i = poz; i >= 1; i -= ub(i)) SUM += AIB[i];
	return SUM;
}

int bsearch(int val) {
	int st = 1, dr = N, mij = 0, SUM = 0, MIN = INT_MAX;
	while(st <= dr) {
		mij = (st + dr) / 2;
		SUM = sum(mij);
		if(SUM == val && mij < MIN) MIN = mij;
		else if (SUM < val) st = mij + 1;
             else dr = mij - 1;
	}
	return MIN;
}

int main() {
	f >> N;
	for(int i = 1; i <= N; i++) add(i, 1);
	NX = N, poz = 2;
	for(int i = 1; i <= N; i++) {
		x = bsearch(poz);
		add(x, -1);
		g << x << " ";
		NX--;
		poz += i;
		if(NX) poz = ((poz % NX == 0)? NX : poz % NX);
	}
	g << "\n";
	return 0;
}