Pagini recente » Cod sursa (job #1521783) | Cod sursa (job #1115822) | Cod sursa (job #3215771) | Cod sursa (job #778206) | Cod sursa (job #1014142)
#include<cstdio>
using namespace std;
int aib[33000], put2;
int v[33000];
int min(int a, int b)
{
if(a < b)
return a;
else
return b;
}
void update(int x)
{
int x2;
x2 = x;
while(x2 <= put2)
{
-- aib[x2];
x2 += (x2 & - x2);
}
}
int query(int poz)
{
int sum = 0, cpoz;
cpoz = poz;
while(cpoz)
{
sum += aib[cpoz];
cpoz -= (cpoz & - cpoz);
}
return sum;
}
int cb(int st, int dr, int val)
{
int med, x, last;
if(val == 0)
val = aib[put2];
while(st <= dr)
{
med = (st + dr) >> 1;
x = query(med);
if(x >= val)
{
last = med;
dr = med - 1;
}
else
st = med + 1;
}
return last;
}
int main()
{
int n, i, poz, misc, j, t, x;
scanf("%d", &t);
for(j = 1; j <= t; ++ j)
{
scanf("%d", &n);
for(i = 1; i <= n; ++ i)
if(i % 2)
aib[i] = 1;
else
aib[i] = aib[i >> 1] << 1;
put2 = 1;
while(put2 < n)
{
put2 = put2 << 1;
}
for(i = n + 1; i <= put2; ++ i)
{
if(i % 2)
aib[i] = 1;
else
aib[i] = aib[i >> 1] << 1;
aib[i] = min(n, aib[i]);
}
poz = 0;
for(i = 2; i <= n; ++ i)
{
x = query(put2) - query(poz);
if(x < i)
poz = cb(1, n, (i - x) % aib[put2]);
else
poz = cb(1, n, i + query(poz));
v[poz] = i - 1;
update(poz);
}
for(i = 1; i <= n; ++ i)
if(v[i])
printf("%d ", v[i]);
else
printf("%d ", n);
for(i = 1; i <= n; ++ i)
v[i] = 0;
printf("\n");
}
return 0;
}