Cod sursa(job #1838138)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 31 decembrie 2016 00:53:38
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <cctype>
#include <unordered_set>
#define MOD 66013
#define pb push_back
#define INF 0x3f3f3f3f
#define INFLL (1LL*INF*INF)
#define ll long long
#define NMAX 30005

using namespace std;

typedef pair<int, int> pii;

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

int aib[NMAX],n;

inline int lsb(int x) {
	return (x&(x-1))^x;
}

void updateBIT(int pos, int val) {
	while(pos<=n) {
		aib[pos]+=val;
		pos+=lsb(pos);
	}
}

int searchBIT(int sum) {
	int p2=1,act=0;

	while(p2<n) p2<<=1;

	while(p2) {
		if(act+p2<=n && aib[act+p2] < sum) {
			sum-=aib[act+p2];
			act+=p2;

			if(sum==0) return act+1;
		}

		p2>>=1;
	}

	return act+1;
}

int main() {
	int pos=2,i,a;

	fin>>n;
	for(i=1;i<=n;++i) updateBIT(i,1);

	fout<<"2 ";
	updateBIT(2,-1);

	for(i=1;i<n;++i) {
		pos+=i;
		pos=pos%(n-i);

		if(pos==0) pos=n-i;
		a=searchBIT(pos);
		fout<<a<<' ';
		updateBIT(a,-1);
	}

	return 0;
}