Cod sursa(job #1425567)

Utilizator justaddcodeJustadd Code justaddcode Data 27 aprilie 2015 18:04:06
Problema Order Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 30004
#define zeros(x) ( (x ^ (x - 1)) & x )
using namespace std;
int n, i, j, st, p, s;
int aib[Nmax];
void add(int x, int y)
{
    int i = 0;
    for (i = x;i <= n; i += zeros(i))
    aib[i] += y;
}
int sum(int x)
{
    int i = 0, suma = 0;
    for (i = x; i >= 1; i -= zeros(i))
    suma += aib[i];
    return suma;
}
int elim()
{
    int pas = 1<<16, i = 0;
    while (pas)
    {
        if (i + pas <= n && sum(i+pas) < s)
        i += pas;
        pas /= 2;
    }
    if (sum(i + 1) == s)
    return i + 1;
}
int main()
{
    freopen("order.in", "r", stdin);
    freopen("order.out", "w", stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    add(i,1);
    s = 1;
    for (i = 1; i <= n; ++i)
    {
        st = sum(n);
        s = (s + i ) % st;
        if (s == 0)
        s = st;
        p = elim();
        printf("%d ", p);
        add(p, - 1);
        --s;
    }
    return 0;
}