Cod sursa(job #3321214)

Utilizator stefan_ciureaStefan Ciurea stefan_ciurea Data 8 noiembrie 2025 16:08:06
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax=3e4+5;

int aib[Nmax],n;

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

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

int bs(int val) {
    int sol=0,s=0;
    for (int pas=(1<<17); pas>0; pas/=2) {
        if (sol+pas<=n && s+aib[sol+pas]<val) {
            s+=aib[sol+pas];
            sol+=pas;
        }
    }
    return sol+1;
}
int main()
{
    ifstream fin("order.in");
    ofstream fout("order.out");
    fin>>n;
    for (int i=1; i<=n; ++i) {
        update(i,1);
    }
    int k=1;
    for (int i=1; i<=n; ++i) {
        k=(k+i)%(n-i+1);
        if (k==0) k=n-i+1;
        int kill=bs(k);
        update(kill,-1);
        fout<<kill<<' ';
        k--;
    }
    fin.close();
    fout.close();
    return 0;
}