Cod sursa(job #2048318)

Utilizator FrequeAlex Iordachescu Freque Data 25 octombrie 2017 22:09:59
Problema Order Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 30000 + 5;

int n, rem, index = 1, last = 2;
int aint[4 * NMAX];

int find_rest(int x, int mod)
{
    int rez = x % mod;
    if (rez == 0)
        return mod;
    return x % mod;
}

void update(int nod, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        aint[nod] += val;
        return;
    }

    int mijl = (st + dr) / 2;

    if (poz <= mijl) update(2 * nod, st, mijl, poz, val);
    else update(2 * nod + 1, mijl + 1, dr, poz, val);

    aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}

int query(int nod, int st, int dr, int a, int b)
{
    if (a <= st && dr <= b)
        return aint[nod];

    int mijl = (st + dr) / 2, rez = 0;

    if (a <= mijl) rez += query(2 * nod, st, mijl, a, b);
    if (b > mijl) rez += query(2 * nod + 1, mijl + 1, dr, a, b);

    return rez;
}

int bin_search(int i)
{
    int st = 1, dr = n, mijl, ans;
    while (st <= dr)
    {
        mijl = (st + dr) / 2;
        if (query(1, 1, n, 1, mijl) >= i)
        {
            dr = mijl - 1;
            ans = mijl;
        }
        else
            st = mijl + 1;
    }

    update(1, 1, n, ans, -1);
    --rem;

    return ans;
}

void read()
{
    fin >> n;
    rem = n;
    for (int i = 1; i <= n; ++i)
        update(1, 1, n, i, 1);
}

int main()
{
    read();
    int x = 2;
    for (int i = 1; i <= n; ++i)
    {
        x = (x + i - 1) % (n - i + 1);
        if (x == 0)
            x = n - i + 1;

        fout << bin_search(x) << " ";
    }

    return 0;
}