Cod sursa(job #3199291)

Utilizator Razvan23Razvan Mosanu Razvan23 Data 1 februarie 2024 12:42:01
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <bits/stdc++.h>
using namespace std;

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

int aib[30005], n;

void Update(int p, int x)
{
    while(p <= n)
    {
        aib[p] += x;
        p += (p &(-p));
    }
}

int Query(int p)
{
    int sum = 0;
    while(p > 0)
    {
        sum += aib[p];
        p -= (p & (-p));
    }
    return sum;
}


int CB(int x)
{
    int p, st, dr, mij;
    st = 1;
    dr = p = n;
    while (st < dr)
    {
        mij = (st + dr) / 2;
        if (x <= Query(mij)) dr = mij;
        else st = mij + 1;
    }
    return dr;
}

int main()
{
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    fout.tie(0);
    fin >> n;
    int i, poz;
    for(i=1; i<=n; i++)
        Update(i, 1);
    poz = 2;
    for(i=1; i<=n; i++)
    {
        poz = (poz + n - 1) % (n - i + 1) + 1;
        int x = CB(poz);
        fout << x << " ";
        Update(x, -1);
    }
    fin.close();
    fout.close();
    return 0;
}