Cod sursa(job #3301901)

Utilizator AswVwsACamburu Luca AswVwsA Data 1 iulie 2025 01:49:10
Problema Farfurii Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <vector>
#include <cassert>
#define ll long long
using namespace std;

const int NMAX = 1e5;

bool seen[NMAX + 1];

ll gauss(int val)
{
    return 1LL * val * (val - 1) / 2;
}

int n;

struct aib
{
    int c[NMAX + 1];
    void update(int poz, int val)
    {
        for (; poz <= n; poz += poz & -poz)
            c[poz] += val;
    }
    int query(int poz)
    {
        int ans = 0;
        for (; poz; poz -= poz & -poz)
            ans += c[poz];
        return ans;
    }
};

aib ds;

int main()
{
    ifstream cin("farfurii.in");
    ofstream cout("farfurii.out");
    int i, j;
    ll k;
    cin >> n >> k;
    int big;
    for (big = 0; (1 << big) <= n; big++);
    big--;
    for (i = 1; i <= n; i++)
        ds.update(i, 1);
    for (i = 1; i <= n; i++)
    {
        ll dif = k - gauss(n - i);
        //query(poz - 1) >= dif
        int ax = 0;
        int sum = 0;
        for (j = big; j >= 0; j--)
            if (ax + (1 << j) <= n and sum + ds.c[ax + (1 << j)] < dif)
            {
                ax += (1 << j);
                sum += ds.c[ax];
            }
        //ax e primul mai mic, ax + 1 e primul mai mare
        //te intereseaza primul 1 dupa ax + 1
        if (dif <= 0)
            ax = 0;
        else
            ax++;
        int ax2 = 0;
        for (j = big; j >= 0; j--)
            if (ax2 + (1 << j) <= n)
            {
                if (ds.c[ax2 + (1 << j)] == 0 or ax2 + (1 << j) <= ax)
                    ax2 += (1 << j);
            }
        ax2++;
        cout << ax2 << " ";
        k -= ds.query(ax2 - 1);
        ds.update(ax2, -1);
    }
}