Pagini recente » Monitorul de evaluare | Cod sursa (job #1422162) | Cod sursa (job #1422103) | Cod sursa (job #3362212) | Cod sursa (job #3362500)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
#define int long long
const int DIM = 1e5;
int n, k, take[DIM + 3];
int aint[4 * DIM + 3];
inline void build(int nod, int st, int dr) {
if(st == dr) aint[nod] = 1;
else {
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
}
inline void update(int nod, int st, int dr, int poz, int val) {
if(st == dr) aint[nod] = val;
else {
int mid = (st + dr) / 2;
if(poz <= mid) update(2 * nod, st, mid, poz, val);
else update(2 * nod + 1, mid + 1, dr, poz, val);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
}
inline int query(int nod, int st, int dr, int x) {
if(st == dr) return st;
else {
int mid = (st + dr) / 2;
if(x <= aint[2 * nod]) return query(2 * nod, st, mid, x);
else return query(2 * nod + 1, mid + 1, dr, x - aint[2 * nod]);
}
}
signed main()
{
///permutarea minim lexico cu k inversiuni
fin >> n >> k;
for(int i=n; i>=1; i--) {
int maxPos = n - i; ///poz i poate crea cu elem de dupa maxim n-i inv
///fac suma = k minim lexico
take[i] = min(k, maxPos);
k -= take[i];
}
///ca sa formez v[i] din take[i] => iau al take[i]+1 lea elem liber
build(1, 1, n);
for(int i=1; i<=n; i++) {
int x = query(1, 1, n, take[i] + 1);
fout << x << " ";
update(1, 1, n, x, 0);
}
return 0;
}