Pagini recente » Cod sursa (job #364958) | Cod sursa (job #1279781) | Cod sursa (job #1901645) | Cod sursa (job #2956563) | Cod sursa (job #2756711)
#include <iostream>
#include <fstream>
#define NMAX 30000
using namespace std;
ifstream fin ("order.in");
ofstream fout ("order.out");
int N;
int pozSterg;
int A, B;
int aib[NMAX + 1];
void buildAIB(){
for(int i = 1; i <= N; i++){
aib[i] = i & (-i);
}
}
void sterg(int poz){
for(int i = poz; i <= N; i += i & (-i)){
aib[i] -= 1;
}
}
int query(int poz){
int rez = 0;
for(int i = poz; i >= 1; i -= i & (-i)){
rez += aib[i];
}
return rez;
}
int newPos(int pos, int q){
q = (q - 1) % query(N) + 1; //tree[1] adica cati am in [1, N]
int lo = pos;
int hi = N + 1;
//de fapt caut in [pos + 1, N]
while(hi - lo > 1){
int mid = lo + (hi - lo) / 2;
A = pos;
B = mid;
if( query(B) - query(A - 1) >= q){
hi = mid;
}
else {
lo = mid;
}
}
//candidatul la raspuns ar trebui sa se afle in hi
if(hi < N + 1){
//inseamna ca exista in [pos + 1, N] solutie
return hi;
}
else {
//inseamna ca nu exista in [pos + 1, N] solutie
//si caut pe [1, pos - 1]
lo = 0;
hi = pos;
while(hi - lo > 1){
int mid = lo + (hi - lo) / 2;
int rez = 0;
A = pos;
B = N;
rez = rez + query(B) - query(A - 1);
A = 1;
B = mid;
rez = rez + query(B) - query(A - 1);
//query(pos, N) + query(1, mid)
if(rez >= q){
hi = mid;
}
else {
lo = mid;
}
}
//acum raspunsul sigur se afla in hi
return hi;
}
}
int main()
{
fin >> N;
buildAIB();
int pos = 1;
for(int q = 1; q <= N; q++){
//vreau sa gasesc acel Z ce reprezinta poz + q
if(q != 1){
sterg(pos);
}
pos = newPos(pos, q);
//prima oara caut in [poz + 1, N]
//dupa care in [1, poz - 1]
fout << pos << ' ';
}
return 0;
}