Cod sursa(job #3325014)

Utilizator Victor321321Victor Casandra Victor321321 Data 24 noiembrie 2025 15:26:13
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

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

int n;
int bit[30005];

void update(int i, int v)
{
    for (; i <= n; i += i & -i)
        bit[i] += v;
}

int find_kth(int k)
{
    int pos = 0;
    int pw = 1 << 15;
    while (pw)
    {
        if (pos + pw <= n && bit[pos + pw] < k)
        {
            k -= bit[pos + pw];
            pos += pw;
        }
        pw >>= 1;
    }
    return pos + 1;
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; ++i) update(i, 1);
    int alive = n;
    int pos = 2;

    for (int step = 1; step <= n; ++step)
    {
        pos = (pos + step - 1) % alive;
        if (pos == 0) pos = alive;
        int idx = find_kth(pos);
        fout << idx << (step == n ? '\n' : ' ');
        update(idx, -1);
        alive--;
        if (alive > 0 && pos > alive) pos = 1;
    }
    return 0;
}