Pagini recente » Cod sursa (job #2338159) | Cod sursa (job #2932054) | Cod sursa (job #678873) | Cod sursa (job #671929) | Cod sursa (job #2952638)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("order.in");
ofstream fout("order.out");
#define DIM 30000
#define Ub(x) (x & -x)
int n;
int aib[DIM + 1];
static inline void Add(int poz, int val) {
for(int i = poz; i <= n; i += Ub(i))
aib[i] += val;
}
static inline int Suma(int poz) {
int s = 0;
for(int i = poz; i >= 1; i -= Ub(i))
s += aib[i];
return s;
}
static inline int CautBinarSt(int x) {
int st = 1, dr = n, poz = 0;
while(st <= dr) {
int mid = (st + dr) >> 1;
int S = Suma(mid);
if(S == x) {
poz = mid;
dr = mid - 1;
}else if(S < x)
st = mid + 1;
else dr = mid - 1;
}
return poz;
}
int main() {
fin >> n;
for(int i = 1; i <= n; i++)
aib[i] = Ub(i); //cati copii am in intervalul [i - 2^k + 1, i];
int pas = 2, nr = n;
for(int i = 1; i <= n; i++) {
int poz = CautBinarSt(pas); //pe cine elimin la pasul pas;
fout << poz << " ";
Add(poz, -1);
pas += i;
nr--;
if(nr)
pas = ((pas % nr) == 0 ? nr : pas % nr);
}
return 0;
}