Cod sursa(job #3364399)

Utilizator RegeleOu3433Calin V. Dragos Andrei RegeleOu3433 Data 2 septembrie 2026 17:14:10
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>
#define lsb(x) (x & -x)

using namespace std;

const int MAXN = 3e4 , MAXP2 = 16384;
struct {
    int a[MAXN + 1] , sz;
    void update ( int poz , int val ) {
        if ( poz <= sz ) {
            a[poz] += val;
            update ( poz + lsb ( poz ) , val );
        }
    }
    int query ( int poz ) {
        if ( poz < 1 )
            return 0;
        return a[poz] + query ( poz - lsb ( poz ) );
    }
    int cautbin ( int k ) {
        int poz , i;

        poz = 0;
        for ( i = MAXP2 ; i > 0 ; i >>= 1 )
            if ( poz + i <= sz && a[poz + i] < k ) {
                k -= a[poz + i];
                poz += i;
            }
        return poz + 1;
    }
} aib;
int main () {
    ifstream fin ( "order.in" );
    ofstream fout ( "order.out" );
    int n , i , poz;

    fin >> n;
    aib.sz = n;
    poz = 1;
    for ( i = 1 ; i <= n ; i++ )
        aib.update ( i , 1 );
    for ( i = 1 ; i <= n ; i++ ) {
        poz = aib.cautbin ( ( i + aib.query ( poz ) - 1 ) % ( n - i + 1 ) + 1 );
        fout << poz << ' ';
        aib.update ( poz , -1 );
    }
    fout.put ( '\n' );
    return 0;
}