Cod sursa(job #1425428)

Utilizator Mr.DoomRaul Ignatus Mr.Doom Data 27 aprilie 2015 14:38:17
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <fstream>
using namespace std;

ifstream is("order.in");
ofstream os("order.out");

const int Nmax = 30001;

int n, byte;
int a[Nmax];

void Insert(int pos, int val);
int Query(int pos);
int BinarySearch(int val, int _byte);

int main()
{
	int val, qn, qi, y = 1;
	is >> n;
	for ( int i = 1; i <= n; ++i )
		Insert(i, 1);
	for ( byte = 1; byte <= n; byte <<= 1 );
	for ( int i = 1; i <= n; ++i )
	{
		qn = Query(n);
		qi = Query(y) + i;
		if ( qi % qn == 0 )
			val = qn;
		else
			val = qi % qn;
		
		y = BinarySearch(val, byte);
		if ( y > n ) y %= n;
		os << y << ' ';
		Insert(y, -1);
		Insert(y + n, -1);
	}
	is.close();
	os.close();
	return 0;
}

void Insert(int pos, int val)
{
	for ( int i = pos; i <= n; i += i & -i )
		a[i] += val;
}

int Query(int pos)
{
	int s = 0;
	for ( int i = pos; i; i -= i & -i )
		s += a[i];
	return s;
}

int BinarySearch(int val, int _byte)
{
	int pos;
	for ( pos = 0; _byte; _byte >>= 1 )
		if ( pos + _byte <= n && a[pos + _byte] < val )
		{
			pos += _byte;
			val -= a[pos];
		}
	return pos + 1;
}