Cod sursa(job #2907117)

Utilizator KarinaDKarina Dumitrescu KarinaD Data 28 mai 2022 19:57:48
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int N = 30000;
int aib[N + 1];

int main ( ) {
    
    int n, i, x, s, pas = 1;
    
    fin >> n;
    
    for ( i = 1; i <= n; i++ ) {
        
        x = i;
        while ( x <= n ){
            aib[x] = aib[x] + 1;
            x = x + ( x & (-x) );
        }
    }
    
    
    for ( int t = 1; t <= n; t++ ){
        
        pas = ( pas + t - 1 ) % ( n - t + 1 );
        
        int st = 0, dr = n + 1, mij;
        
        while ( dr - st > 1 ) {
            
            mij = ( dr + st ) / 2;
            
            s = 0;
            x = mij;
            
            while ( x > 0 ){
                s = s + aib[x];
                x = x - ( x & (-x) );
            }
            
            if ( s < pas + 1 )
                st = mij;
            else
                dr = mij;
        }
        
        st++;
        
        
        fout << st << " ";
        
        while ( st <= n ){
            aib[st] = aib[st] - 1;
            st = st + ( st & (-st) );
        }
        
    }
    
    return 0;
}