Cod sursa(job #2945375)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 23 noiembrie 2022 18:56:30
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int aib[30001];

void update (int pos, int val)
{
    for (int i=pos; i<=n; i += i & -i)
        aib[i] += val;
}

int query (int pos)
{
    int ret = 0;

    for (int i=pos; i>0; i -= i & -i)
        ret += aib[i];
    return ret;
}

int main()
{
    in >> n;

    for (int i=1; i<=n; i++)
        update(i, 1);
    int pos = 2;
    for (int i=1; i<=n; i++)
    {
        pos = (pos + i - 1) % (n - i + 1);
        if (pos == 0)
            pos = n - i + 1;

        int l=1, r=n;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (query(mid) >= pos)
                r = mid;
            else
                l = mid + 1;
        }

        out << r << ' ';
        update(r, -1);
    }

    return 0;
}