Pagini recente » Cod sursa (job #2716843) | Cod sursa (job #2971360) | Cod sursa (job #2681619) | Cod sursa (job #744232) | Cod sursa (job #3247941)
#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;
}