Cod sursa(job #3247941)

Utilizator CosminaneBoac Mihai Cosmin Cosminane Data 9 octombrie 2024 22:35:34
Problema Order Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <iostream>
using namespace std;
int v[30005], n;
void modif( int x, int a ){
    int poz, i;
    x--;
    poz = x;
    i = 0;
    while( poz < n ){
        if( x % 2 == 0 ){
            v[poz] += a;
            poz += ( 1 << i );
        }
        x /= 2;
        i++;
    }
}
int get( int x ){
    int poz, i, s;
    poz = x - 1;
    s = i = 0;
    while( x > 0 ){
        if( x % 2 == 1 ){
            s += v[poz];
            poz -= ( 1 << i );
        }
        x /= 2;
        i++;
    }
    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;
}