Cod sursa(job #3258453)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 22 noiembrie 2024 15:12:32
Problema Order Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <bits/stdc++.h>
using namespace std;
int v[30005], n;
void modif( int x, int a ){
    for( ; x <= n; x += x & -x ){
        v[x] += a;
    }
}
int get( int x ){
    int s = 0;
    for( ; x > 0; x -= x & -x ){
        s += v[x];
    }
    return s;
}
int sum( int st, int dr ){
    return get( dr ) - get( st - 1 );
}
int get_sum( int st, int dr, int tip ){
    int m_st, m_dr;
    m_st = ( st - 1 ) % n + 1;
    m_dr = ( dr - 1 ) % n + 1;
    if( tip == 1 ){
        ///cout << st << ' ' << dr << ' ';
    }
    if (m_st <= m_dr) {
        return sum( m_st, m_dr ) + ( dr - st + 1 ) / n * sum( 1, n );
    }
    else {
        return sum( m_st, n ) + sum( 1, m_dr ) + ( dr - ( st + n - ( m_st - m_dr ) ) + 1) / n * sum(1, n);
    }
}
int main(){
    int i, poz, st, dr, mij;
    ifstream fin( "order.in" );
    ofstream fout( "order.out" );
    fin >> n;
    poz = 1;
    for( i = 1; i <= n; i++ ){
        st = 0;
        dr = n * n;
        while( dr - st > 1 ){
            mij = ( st + dr ) / 2;
            ///cout << i << ' ' << st << ' ' << dr << ' ' << mij << '\n';
            ///cout << i << ' ' << ' ' << get_sum( poz + 1, poz + mij, 1 ) << '\n';
            if( mij == 0  || mij - get_sum( poz + 1, poz + mij, 0 ) < i ){
                st = mij;
            }
            else{
                dr = mij;
            }
        }
        poz = ( poz + dr - 1 ) % n + 1;
        fout << poz << ' ';
        modif( poz, 1 );
        ///cout << '\n';
    }
    return 0;
}