Cod sursa(job #2714572)

Utilizator KlinashkaDiacicov Calin Marian Klinashka Data 2 martie 2021 00:05:41
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>
using namespace std;

const int NMAX = (int)1e5;
int tree[4*NMAX];

void build(int v, int st, int dr) {
    if(st==dr) {
        tree[v] = 1;
        return;
    }
    int mj=(st+dr)/2;
    build(2*v, st, mj);
    build(2*v+1, mj+1, dr);
    tree[v] = tree[2*v]+tree[2*v+1];
}

// scot elem. din set
void update(int v, int st, int dr, int i) { 
    if(st>i || dr<i)
        return;
    if(st==dr) {
        tree[v] = 0;
       // cout << tree[v] << '\n';
        return;
    }
    int mj = (st+dr)/2;
    update(2*v, st, mj, i);
    update(2*v+1, mj+1, dr, i);
    tree[v] = tree[2*v]+tree[2*v+1];
}

int query(int v, int st, int dr, long long k) {
    //cout << st << ' ' << dr << ' ' << k << '\n';
    if(st==dr)
        return st;
    int mj=(st+dr)/2;
    if(tree[2*v]>=k)
        return query(2*v, st, mj, k);
    return query(2*v+1, mj+1, dr, k-tree[2*v]);
}

void debug(int v, int st, int dr) {
    cout << tree[v] << ' ' << st << ' ' << dr << '\n';
    if(st<dr) {
        debug(2*v, st, (st+dr)/2);
        debug(2*v+1, (st+dr)/2+1, dr);
    }
}

// 1 2 ... n --> permutarea minima lexicografic a.i. nr inversiuni sa fie k
int main() {
    freopen("farfurii.in", "r", stdin);
    freopen("farfurii.out", "w", stdout);
    long long k;
    int n;
    vector<int> sol;
    cin >> n >> k;
    build(1, 1, n);
    for(int i=1;i<=n;i++) {
       // cout << k << ' ';
        long long mn = (n-i)*(n-i-1)/2;
        long long cnt = max(1LL, k-mn+1);
        int j = query(1, 1, n, cnt);
        sol.push_back(j);
        update(1, 1, n, j);
        cnt--;
        k-=cnt;
    }
    for(auto a:sol)
       cout << a << ' ';
    return 0;
}