Pagini recente » Cod sursa (job #1107718) | Cod sursa (job #1097228) | Cod sursa (job #1252689) | Cod sursa (job #149788) | Cod sursa (job #2590545)
#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 query ( int poz );
int search ( int start, 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::query ( int poz ) {
int ans = 0;
while ( poz ) {
ans += aib[poz];
poz = poz - ( poz & ( poz - 1 ) ^ poz );
}
return ans;
}
int BinTree::search ( int start, int val ) {
int sum = query ( N ) - query ( start );
if ( sum < val )
return search ( 0, val - sum );
int pas = 1<<16;
int ans = start;
while ( pas ) {
if ( ans + pas <= N && query ( ans + pas ) - query ( start ) < val )
ans += pas;
pas /= 2;
}
return ans + 1;
}
int main() {
BinTree arbore = BinTree();
int start = 1;
for ( int i = 1; i <= NR; ++i ) {
start = arbore.search ( start, i % ( NR - i + 1 ) );
fout << start << ' ';
arbore.update ( start, -1 );
}
fin.close();
fout.close();
return 0;
}