Pagini recente » Cod sursa (job #1109679) | Cod sursa (job #280261) | Cod sursa (job #2981697) | Cod sursa (job #1322252) | Cod sursa (job #2578030)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
bool used[100005];
int aib[400005];
int n, f, i;
void update(int poz, int val) {
while(poz <= n) {
aib[poz] += val;
poz += (poz&-poz);
}
}
int query(int poz) {
int s = 0;
while(poz > 0) {
s += aib[poz];
poz -= (poz&-poz);
}
return s;
}
int cb(int val) {
int st = 1, dr = n;
while(st <= dr) {
int m = (st+dr)/2;
//cout <<"da ";
int q = query(m);
//cout << st << ' ' << dr << ' ' << q << ' ' << val << '\n';
if(q == val && query(m-1) < val)
return m;
else if(q >= val)
dr = m-1;
else
st = m+1;
}
return -1;
}
void solve() {
for(i = 1; i <= n; i++) {
long long inv = 1LL*(n-i)*(n-i-1)/2;
if(inv > f)
fout << i << ' ';
else
break;
}
for(int k = i; k <= n; k++)
update(k, 1);
for(int k = i; k <= n; k++) {
long long inv = 1LL*(n-k)*(n-k-1)/2;
int poz = cb(f-inv+1);
fout << poz << ' ';
update(poz, -1);
f = inv;
}
}
int main() {
fin >> n >> f;
solve();
}