Pagini recente » Cod sursa (job #2852836) | Cod sursa (job #1322055)
#include <algorithm>
#include <fstream>
using namespace std;
const int NMAX= 100000;
ifstream in( "order.in" );
ofstream out( "order.out" );
int aib[NMAX+1], N, poz= 1;
inline int lsb( int x )
{
return x & -x;
}
void update( int pos, int val )
{
for( int i= pos; i<=N; i+= lsb( i ) )
{
aib[i]+=val;
}
}
int querry( int pos )
{
int ans= 0;
for( int i= pos; i>0; i-= lsb( i ) )
{
ans+=aib[i];
}
return ans;
}
int binary(int x, int y, int val)
{
int last, ans= 0, sc= 0, t= querry( x-1 );
for( int i= 1<<17; i>0; i>>=1 )
{
if( ans+i<=N )
{
if( sc + aib[ans+i] - t < val )
{
ans+= i;
sc+= aib[ans];
}
else if( sc + aib[ ans+i ] - t==val )
last= ans+i;
}
}
return last;
}
int main()
{
in >> N;
for( int i= 1; i<=N; ++i )
{
update( i, 1 );
}
for( int i= 1; i<=N; ++i )
{
int lg=( i-1 )%( N-i+1 )+1, limit= querry( N ) - querry( poz );
if(lg<=limit)
{
poz= binary( poz+1, N, lg );
}
else
{
poz= binary( 1, poz, lg-limit );
}
update( poz, -1 );
out << poz << " ";
}
return 0;
}