Cod sursa(job #2922207)

Utilizator IvanAndreiIvan Andrei IvanAndrei Data 6 septembrie 2022 09:03:27
Problema Order Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>

using namespace std;

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

#define zeros(x)(x & (-x))

const int max_size = 3e4 + 1;

int aib[max_size], n;

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

int querry (int poz)
{
    int ans = 0;
    for (int i = poz; i > 0; i -= zeros(i))
    {
        ans += aib[poz];
    }
    return ans;
}

int main ()
{
    int e = 1;
    in >> n;
    while (e <= n)
    {
        e *= 2;
    }
    e /= 2;
    for (int i = 1; i <= n; i++)
    {
        update(i, 1);
    }
    int poz = 2;
    for (int i = 1; i <= n; i++)
    {
        poz = (poz + i - 1) % (n - i + 1);
        if (poz == 0)
        {
            poz = n - i + 1;
        }
        int ec = e, st = 0;
        while (ec >>= 1)
        {
            if (querry(st + ec) < poz)
            {
                st += ec;
            }
        }
        while (querry(st) < poz)
        {
            st++;
        }
        out << st << " ";
        update(st, -1);
    }
    in.close();
    out.close();
    return 0;
}