Pagini recente » Cod sursa (job #1200972) | Jobs | Cod sursa (job #2636377) | Cod sursa (job #2746384) | Cod sursa (job #2748463)
#include <iostream>
#include <fstream>
using namespace std;
const int NMAX = 30001;
ifstream fin("order.in");
ofstream fout("order.out");
int AIB[NMAX], N;
void Update( int pos, int val ){
while( pos <= N)
{
AIB[pos] += val;
pos += ( pos & -pos );
}
}
int Query( int pos ){
int sum = 0;
while( pos )
{
sum += AIB[pos];
pos -= ( pos & -pos );
}
return sum;
}
int BS( int lf, int rg, int val ){
if( lf > rg )
return 200000000;
int mid = lf + ( rg - lf ) / 2;
//cout << lf << ' ' << rg << ' ' << mid << ' ' << Query( mid ) << '\n';
if( Query( mid ) > val )
return BS( lf, mid-1, val );
if( Query( mid ) < val )
return BS( mid+1, rg, val );
return min( mid, BS( lf, mid-1, val ) );
}
int main()
{
fin >> N;
for( int i = 1; i <= N; ++i )
Update( i, 1 );
int index = 1;
int val, end_sum;
for( int i = 1; i <= N; ++i )
{
val = i;
//cout << Query(N) << '-' << Query(index) << '\n';
end_sum = Query(N) - Query(index);
//cout << val << '\n';
if( end_sum < val )
{
//cout << end_sum << ":\n";
val -= end_sum;
index = 0;
end_sum = Query(N);
val = val % end_sum;
if( !val ) val = end_sum;
}
//cout << val << '+' << Query(index) << '\n';
index = BS( index+1, N, val + Query(index) );
Update( index, -1 );
//cout << index << '\n';
fout << index << ' ';
}
}