Pagini recente » Cod sursa (job #1295013) | Cod sursa (job #247392) | Cod sursa (job #2953406) | Cod sursa (job #1410253) | Cod sursa (job #2384825)
#include <fstream>
#include <vector>
using namespace std;
ifstream fin( "order.in" );
ofstream fout( "order.out" );
const int NMAX = 30005;
const int INF = 2000000000;
int N;
int tree[NMAX];
vector <int> sol;
void Read()
{
fin >> N;
fin.close();
}
int Query( int pos )
{
int sum = 0;
while( pos > 0 )
{
sum += tree[pos];
pos -= pos & -pos;
}
return sum;
}
void Update( int pos, int val )
{
while( pos <= N )
{
tree[pos] += val;
pos += pos & -pos;
}
}
int BinSearch( int lf, int rg, int val )
{
if( lf > rg ) return INF;
int mid = ( lf + rg ) / 2;
int q = Query( mid );
//fout << mid << ' ' << q << '\n';
if( q == val ) return min( mid, BinSearch( lf, mid - 1, val ) );
if( q > val ) return BinSearch( lf, mid - 1, val );
else return BinSearch( mid + 1, rg, val );
}
void Do()
{
int curent, target;
int p;
for( int i = 1; i <= N; ++i )
Update( i, 1 );
sol.push_back( 2 );
Update( 2, -1 );
curent = 2;
for( int i = 2; i <= N; ++i )
{
int qN = Query( N ), qC = Query( curent );
if( qN - qC >= i )
{
target = qC + i;
p = BinSearch( curent + 1, N, target );
sol.push_back( p );
Update( p, -1 );
curent = p;
}
else
{
target = ( qC + i ) % qN ;
if( target == 0 ) target = qN;
p = BinSearch( 1, N, target );
sol.push_back( p );
Update( p, -1 );
curent = p;
}
}
for( int i = 0; i < sol.size(); ++i )
fout << sol[i] << ' ';
}
int main()
{
Read();
Do();
return 0;
}