Pagini recente » Cod sursa (job #256909) | Cod sursa (job #2701244) | Cod sursa (job #136902) | Cod sursa (job #1422984) | Cod sursa (job #3258453)
#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;
}