Pagini recente » Cod sursa (job #7728) | Cod sursa (job #641619) | Cod sursa (job #521829) | Cod sursa (job #272102) | Cod sursa (job #2672503)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin("order.in");
ofstream cout("order.out");
#define NMAX 30001
#define Ub(x) (x & (-x))
int aib[NMAX], n, pas, i, nr;
void scad(int pos) {
for(int i = pos; i <= n; i += Ub(i))
aib[i]--;
}
int suma(int pos) {
int i, s = 0;
for(i = pos; i >= 1; i -= Ub(i))
s += aib[i];
return s;
}
int cautBinar(int x) {
int st = 1, dr = n, pos = NMAX;
while(st <= dr) {
int mid = (st + dr) / 2;
int sum = suma(mid);
if(sum == x && mid < pos)
pos = mid;
else if(x <= sum)
dr = mid - 1;
else st = mid + 1;
}
return pos;
}
int main() {
cin >> n;
for(i = 1; i <= n; i++) //cate pozitii am libere pana la i
aib[i] = Ub(i);
pas = 2, nr = n;
for(i = 1; i <= n; i++) {
int x = cautBinar(pas); //caut cel mai din st indice cu suma egala cu nr de pasi
cout << x << " " ;
scad(x); //scad cati raman pana la fiecare pozitie;
nr--; //scad nr de copii;
pas += i;
if(nr)
pas %= nr;
if(pas == 0)
pas = nr;
}
return 0;
}