Pagini recente » Cod sursa (job #875271) | Cod sursa (job #2112880) | Cod sursa (job #1409205) | Cod sursa (job #1225359) | Cod sursa (job #1216043)
#include <fstream>
const char IN [ ] = "order.in" ;
const char OUT [ ] = "order.out" ;
const int MAX = 30014 ;
using namespace std ;
ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;
int v [ MAX * 4 ];
void build ( int nod , int st , int dr )
{
if ( st == dr )
{
v [ nod ] = 1 ;
return ;
}
int mij = ( st + dr ) / 2 ;
build( nod * 2 , st , mij ) ;
build( nod * 2 + 1, mij + 1 , dr ) ;
v [ nod ] = v [ nod * 2 ] + v [ nod * 2 + 1 ] ;
}
void update ( int nod , int st , int dr , int poz )
{
if ( st == dr )
{
v [ nod ] = 0 ;
return ;
}
int mij = ( st + dr ) / 2 ;
if ( poz <= v [ nod * 2 ] )
update( nod * 2 , st , mij , poz );
else update ( nod * 2 + 1 , mij + 1 , dr , poz - v [ nod * 2 ] ) ;
v [ nod ] = v [ nod * 2 ] + v [ nod * 2 + 1 ];
}
int Query ( int nod , int st , int dr , int poz )
{
if ( st == dr )
{
return st ;
}
int mij = ( st + dr ) / 2 ;
if ( poz <= v [ nod * 2 ] )
return Query( nod * 2 , st , mij , poz );
else return Query( nod * 2 + 1 , mij + 1 , dr , poz - v [ nod * 2 ] ) ;
}
int main ( )
{
int n ;
fin >> n ;
build( 1 , 1 , n ) ;
int elimin = 2 ;
int ramas = n ;
for ( int i = 1 ; i <= n ; ++ i , -- ramas )
{
elimin = ( elimin + i - 1 ) % ramas ;
if ( ! elimin )
elimin = 1 ;
int poz = Query( 1 , 1 ,n , elimin );
fout << poz << ' ' ;
update( 1 , 1 , n , elimin ) ;
}
return 0 ;
}