Cod sursa(job #3271905)

Utilizator Alex_BerbescuBerbescu Alexandru Alex_Berbescu Data 27 ianuarie 2025 19:08:21
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll lsb(ll x)
{
   return ((x ^ (x - 1)) & x);
}
const int dim = 1e5 + 55;
ll n, x, poz, aib[dim], k, rest;
ll query(ll poz)
{
    ll sum = 0;
    for(; poz > 0; poz -= lsb(poz))
       sum += aib[poz];
    return sum;

}
void add(ll poz, ll val)
{
    for(; poz <= n; poz += lsb(poz))
        aib[poz] += val;
}
ll cb(ll val)
{
    ll st = 1, dr = n, mid = 0, sol = 0;
    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(query(mid) >= val)
        {
            sol = mid;
            dr = mid - 1;

        }
        else
        {
            st = mid + 1;
        }
    }
    return sol;
}
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

int32_t main()
{
    fin >> n >> k;
    for(int i = 1; i <= n; ++i)
        aib[i] = lsb(i);
    for(ll i = 1; i <= n; ++i)
    {
        rest = 1ll * (n - i) * (n - i - 1) / 2;
        if(rest > k)
        {
            ll ct = cb(1);
            fout << ct << " ";
            add(ct, -1);

        }
        else
        {
            ll ct = cb(k - rest + 1);
            fout << ct << " ";
            add(ct, -1);
            k = rest;
        }
    }
    return 0;
}