Cod sursa(job #3267147)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 11 ianuarie 2025 10:01:32
Problema Order Scor 100
Compilator cpp-64 Status done
Runda cex_6 Marime 0.96 kb
#include <bits/stdc++.h>
#define ub(x) (x&(-x))

using namespace std;

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

const int NMAX=2e5+5;
int n, sol[NMAX], aib[NMAX];

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

int query (int poz)
{
    int s=0;
    for (int i=poz; i>=1; i-=ub(i))
        s+=aib[i];
    return s;
}

int cb (int n, int val)
{
    int st=1, dr=n;
    while (st<dr)
    {
        int mij=(st+dr)/2;
        if (query(mij)>=val)
            dr=mij;
        else
            st=mij+1;
    }
    return st;
}

int main()
{
    fin >> n;
    for (int i=1; i<=n; i++)
        update(i,1);
    int j=2, p=n;
    for (int i=1; i<=n; i++)
    {
        int x=cb(n,j);
        sol[i]=x;
        update(x,-1);
        p--;
        j+=i;
        if (p)
            j=(j-1)%p+1;
    }
    for (int i=1; i<=n; i++)
        fout << sol[i] << " ";
    return 0;
}