Pagini recente » Cod sursa (job #571737) | Cod sursa (job #1845477) | Cod sursa (job #2935874) | Cod sursa (job #507955) | Cod sursa (job #2690750)
#include <iostream>
#include <cstdio>
using namespace std;
const int NMAX = 100000;
int n, k;
int aint[2 * NMAX + 5];
void update(int poz) {
aint[poz += n - 1] = 1;
for(poz >>= 1; poz; poz >>= 1)
aint[poz] = aint[poz << 1] + aint[poz << 1 | 1];
}
int query(int poz) {
int sum = 0;
for(int st = n, dr = poz + n - 1; st <= dr; st >>= 1, dr >>= 1) {
if(st & 1)
sum += aint[st++];
if(!(dr & 1))
sum += aint[dr--];
}
return sum;
}
int get_poz(int i) {
return max((long long)k - (long long)(n - i) * (n - i - 1) / 2 + 1, (long long)1);
}
int get_nr(int poz) {
int st = 1, dr = n;
while(st <= dr) {
int mij = (st + dr) / 2, cpoz = mij - query(mij);
if(cpoz < poz)
st = mij + 1;
else if(cpoz > poz || aint[mij + n - 1] == 1)
dr = mij - 1;
else
return mij;
}
return -1;
}
int main() {
freopen("farfurii.in", "r", stdin);
freopen("farfurii.out", "w", stdout);
scanf("%d %lld", &n, &k);
for(int i = 1; i <= n; i++) {
int p = get_poz(i), nr = get_nr(p);
printf("%d ", nr);
update(nr);
k -= p - 1;
}
return 0;
}