Pagini recente » Cod sursa (job #2325467) | Cod sursa (job #2894341) | Cod sursa (job #2185453) | Cod sursa (job #2672163) | Cod sursa (job #2756708)
#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 tree[4 * NMAX + 1];
void buildArbore(int node, int left, int right){
tree[node] = right - left + 1;
if(left == right){
return;
}
int mid = left + (right - left) / 2;
buildArbore(node * 2, left, mid);
buildArbore(node * 2 + 1, mid + 1, right);
}
void sterg(int node, int left, int right){
if(left == right){
tree[node] = 0;
return;
}
int mid = left + (right - left) / 2;
if(pozSterg <= mid){
sterg(node * 2, left, mid);
}
else {
sterg(node * 2 + 1, mid + 1, right);
}
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int query(int node, int left, int right){
if(A <= left && right <= B){
return tree[node];
}
int mid = left + (right - left) / 2;
int rez1 = 0, rez2 = 0;
if(A <= mid){
rez1 = query(node * 2, left, mid);
}
if(B >= mid + 1){
rez2 = query(node * 2 + 1, mid + 1, right);
}
return rez1 + rez2;
}
int newPos(int pos, int q){
q = (q - 1) % tree[1] + 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(1, 1, N) >= 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(1, 1, N);
A = 1;
B = mid;
rez = rez + query(1, 1, N);
//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;
buildArbore(1, 1, N);
int pos = 1;
for(int q = 1; q <= N; q++){
//vreau sa gasesc acel Z ce reprezinta poz + q
if(q != 1){
pozSterg = pos;
sterg(1, 1, N);
}
pos = newPos(pos, q);
//prima oara caut in [poz + 1, N]
//dupa care in [1, poz - 1]
fout << pos << ' ';
}
return 0;
}