Cod sursa(job #3361971)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 31 iulie 2026 01:55:21
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <bits/stdc++.h>
#define int long long
#define ub(x) x&(-x)

using namespace std;

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

const int nmax = 3e4 + 5;

int n, aib[nmax];

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

int bs (int val)
{
    int origin = 0;
    for (int bit = 1 << 18; bit; bit >>= 1)
    {
        if (origin + bit <= n && aib[origin + bit] < val)
        {
            origin += bit;
            val -= aib[origin];
        }
    }
    return origin + 1;
}

signed main ()
{
    ios::sync_with_stdio (false);
    cin.tie (nullptr);

    fin >> n;
    for (int i = 1; i <= n; i++)
        update (i, 1);
    int j = 2;
    for (int i = 1; i <= n; i++)
    {
        j = (j + i - 1) % (n - i + 1);
        if (j == 0)
            j = n - i + 1;
        int poz = bs (j);
        fout << poz << " ";
        update (poz, -1);
    }
    return 0;
}