Pagini recente » Cod sursa (job #2417541) | Cod sursa (job #1685385) | Cod sursa (job #2978275) | Cod sursa (job #2365196) | Cod sursa (job #2590549)
#include <iostream>
#include <fstream>
std::ifstream fin ( "order.in" );
std::ofstream fout ( "order.out" );
const int NMAX = 30000;
int NR;
class BinTree {
private :
int N;
int v[1 + NMAX];
int aib[1 + NMAX];
public :
BinTree();
~BinTree(){};
void update ( int poz, int val );
int search ( int val );
};
BinTree::BinTree ( ) {
fin >> N;
NR = N;
for ( int i = 1; i <= N; ++i ) {
v[i] = 1;
update ( i, v[i] );
}
}
void BinTree::update ( int poz, int val ) {
while ( poz <= N ) {
aib[poz] += val;
poz = poz + ( poz & ( poz - 1 ) ^ poz );
}
}
int BinTree::search ( int val ) {
int pas = 1<<16;
int ans = 0;
while ( pas ) {
if ( ans + pas <= N && aib[ans + pas] < val ) {
ans += pas;
val -= aib[ans];
}
pas /= 2;
}
return ans + 1;
}
int main() {
BinTree arbore = BinTree();
int start = 1;
for ( int i = 1; i <= NR; ++i ) {
start = ( start + i - 1) % ( NR - i + 1 ) + 1;
int ans = arbore.search ( start );
fout << ans << ' ';
arbore.update ( ans, -1 );
--start;
}
fin.close();
fout.close();
return 0;
}