Cod sursa(job #2946308)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 24 noiembrie 2022 18:49:44
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <bits/stdc++.h>
#define LIM 1<<17
/// TONI BO$$ was here
/// #MLC

using namespace std;

int aint[400001];

void build(int st, int dr, int cur){
    if(st == dr){
        aint[cur] = 1;
        return ;
    }
    int mid = (st + dr) / 2;
    build(st, mid, cur * 2);
    build(mid + 1, dr, cur * 2 + 1);
    aint[cur] = aint[cur * 2] + aint[cur * 2 + 1];
}

void update(int st, int dr, int cur, int x){
    if(st == dr){
        aint[cur] = 0;
        return ;
    }
    int mid = (st + dr) / 2;
    if(mid >= x)
        update(st, mid, cur * 2, x);
    else
        update(mid + 1, dr, cur * 2 + 1, x);
    aint[cur] = aint[cur * 2] + aint[cur * 2 + 1];
}
/// interogatiile se fac pe intervalul [1...x] , cu alte cuvinte vrem sa vedem cate elemente exista (nemarcate) in intervalul [1...x]
int query(int st, int dr, int cur, int x){
    if(st == dr)
        return aint[cur];
    if(dr <= x) /// [st, dr] E [1..x] => dr <= x
        return aint[cur];
    int mid = (st + dr) / 2, sol = 0;
    if(mid >= x)
        sol = query(st, mid, cur * 2, x);
    else
    {
        sol = query(st, mid, cur * 2, x);
        sol += query(mid + 1, dr, cur * 2 + 1, x);
    }
    return sol;
}


int main()
{
    int i, pas, j, n;
    long long k, z;
    freopen("farfurii.in","r",stdin);
    freopen("farfurii.out","w",stdout);
    scanf("%d%lld", &n, &k);
    build(1, n, 1);
    for(i = 1; i <= n; i++){
        z = k - 1LL * (n - i) * (n - i - 1) / 2;
        int pos;
        if(z <= 0) pos = 1;
        else pos = z + 1;
        k -= (pos - 1);
        pas = 1 << 16;
        j = 0;
        while(pas){
            if(j + pas <= n && query(1, n, 1, j + pas) < pos)
                j += pas;
            pas /= 2;
        }
        printf("%d ", j + 1);
        update(1, n, 1, j + 1);
    }

    return 0;
}