Pagini recente » Cod sursa (job #549158) | Cod sursa (job #3210997) | Cod sursa (job #2965041) | Cod sursa (job #443973) | Cod sursa (job #3323299)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
int N;
int sumT;
int eliminati[60000];
int lsb(int x) {
return x & (-x);
}
void debug_aib() {
for(int i = 1; i <= 32; i++)
cout << i << ": " << eliminati[i] << '\n';
}
void bump(int pos, int val) {
for(int i = pos; i <= 1 << 15; i += lsb(i))
eliminati[i] += val;
}
int sum(int pos) {
int sum = 0;
for(int i = pos; i >= 1; i -= lsb(i)){
sum += eliminati[i];
}
return sum;
}
int shiftf(int spos, int locuri) {
int sumi = sum(spos);
int pos = 0;
int sum = 0;
do {
pos = 0;
for (int pas = 1 << 15; pas >= 1; pas /= 2){
//cout << pas << " sum: " << sum << " to add: " << eliminati[pos + pas] << '\n';
if(sum + eliminati[pos + pas] - sumi < locuri &&
pos + pas <= N) {
sum += eliminati[pos + pas];
pos += pas;
//cout << "stepped " << pas << '\n';
}
}
} while (pos >= N);
return pos + 1;
}
int main(){
fin >> N;
for(int i = 1; i <= N; i++){
eliminati[i] += lsb(i);
}
//debug_aib();
int pos = 1;
sumT = N;
for(int i = 1; i <= N; i++){
pos = shiftf(pos, i);
bump(pos, -1);
sumT--;
fout << pos << ' ';
}
return 0;
}