Cod sursa(job #2477517)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 20 octombrie 2019 15:23:08
Problema Order Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 30000 + 7;
int n, aib[N];

void add(int i, int x)
{
        while (i <= n)
        {
                aib[i] += x;
                i += i & (-i);
        }
}

int prefix(int i)
{
        int r = 0;
        while (i)
        {
                r += aib[i];
                i -= i & (-i);
        }
        return r;
}

int first(int k)
{
        int r = 0, step = (1 << 15);
        while (step)
        {
                if (r + step <= n && aib[r + step] < k)
                {
                        r += step;
                        k -= aib[r];
                }
                step /= 2;
        }
        r++;
        return r;
}

int main()
{
        freopen ("order.in", "r", stdin);
        freopen ("order.out", "w", stdout);

        scanf("%d", &n);

        for (int i = 1; i <= n; i++)
                add(i, +1);

        int x = 1;
        for (int j = 1; j <= n; j++)
        {
                int i = j % (n - j + 1);
                i += !i;
                int pn = prefix(n), px = prefix(x);
                if (pn - px >= i)
                        x = first(px + i);
                else
                        x = first(px - pn + i);
                printf("%d ", x);
                add(x, -1);
        }
        printf("\n");
}