Cod sursa(job #1266064)

Utilizator AndreeaBaltaBalta Andreea Cristina AndreeaBalta Data 18 noiembrie 2014 10:26:03
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <cstdio>

using namespace std;

const int N = 30005;

int aib[30005], n;
inline int lsb(int x)
{
	return x & -x;
}

void update(int poz, int val)
{
	for(;poz <= n; poz += lsb(poz))
		aib[poz] += val;
}

int query(int b)
{
	int s = 0;
	for(;b; b -= lsb(b))
		s+= aib[b];
	return s;
}

int bs(int val)
{
	int st = 1, dr = n, med, last = -1;
	while(st <= dr)
	{
		med = (st + dr) >> 1;
		if(query(med) >= val)
		{
			dr = med - 1;
		}
		else
			st = med + 1;
	}
	return st;
}

int main()
{
    FILE *in, *out;
    in = fopen("order.in", "r");
    out = fopen("order.out", "w");
    register int i, p = 1;
    int nr;
    fscanf(in, "%d", &n);
    for(i = 1; i <= n; i++)
        update(i, 1);
    for(i = 1; i <= n; i++)
    {
        p += i;
        p %= (n - i + 1);
        if(!p)
            p = n - i + 1;
        nr = bs(p);
        update(nr, -1);
        p = query(nr);
        fprintf(out, "%d ", nr);
    }
    return 0;
}