Cod sursa(job #2578066)

Utilizator vlad082002Ciocoiu Vlad vlad082002 Data 10 martie 2020 14:30:43
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <fstream>
#include <iostream>
using namespace std;

ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

bool used[100005];
long long aib[100005];
long long n, f, i;

void update(long long poz, long long val) {
    while(poz <= n) {
        aib[poz] += val;
        poz += (poz&-poz);
    }
}

long long query(long long poz) {
    long long s = 0;
    while(poz > 0) {
        s += aib[poz];
        poz -= (poz&-poz);
    }
    return s;
}

long long cb(long long val) {
    long long st  = 1, dr = n;
    while(st <= dr) {
        long long m = (st+dr)/2;
        long long q = query(m);
        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(long long k = i; k <= n; k++)
        update(k, 1);

    for(long long k = i; k <= n; k++) {
        long long inv = 1LL*(n-k)*(n-k-1)/2;
        long long poz = cb(f-inv+1);
        fout << poz << ' ';
        update(poz, -1);
        f = inv;
    }
}

int main() {
    fin >> n >> f;
    solve();
}