Cod sursa(job #3267382)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 11 ianuarie 2025 11:20:30
Problema Order Scor 100
Compilator cpp-64 Status done
Runda cex_6 Marime 1.11 kb
#include <algorithm>
#include <fstream>
#include <vector>
#include <map>

using namespace std;

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

const int nmax = 30005;
int n, m, aib[nmax], v[nmax], ans[nmax];

int ub(int x){
    return (x&(-x));
}

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

int sum(int poz)
{
    int ans = 0;
    for(int i = poz; i >= 1; i -= ub(i))
        ans += aib[i];

    return ans;
}

int binse(int st, int dr, int val)
{
    int poz = 0;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(sum(mij) >= val)
            poz = mij, dr = mij - 1;
        else
            st = mij + 1;
    }

    return poz;
}

int main()
{
    f >> n;
    for(int i = 1; i <= n; i ++)
        add(i, 1);

    int ind = 2; m = n;
    for(int i = 1; i <= n; i ++)
    {
        ans[i] = binse(1, n, ind);
        add(ans[i], -1);

        m --;
        if(m)
            ind = (ind - 1 + i) % m + 1;
    }

    for(int i = 1; i <= n; i ++)
        g << ans[i] << " ";
    return 0;
}