Cod sursa(job #3328328)

Utilizator Luca_georgescuLuca Georgescu Luca_georgescu Data 7 decembrie 2025 19:11:55
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("farfurii.in");
ofstream g("farfurii.out");

const int nmax=1e5+5;
int aib[nmax];
int n,k;

struct AINT
{
    void update(int i, int x)
    {
        while ( i<=n )
        {
            aib[i]+=x;
            i+=(i&-i);
        }
    }

    int query(int i)
    {
        int sum=0;

        while ( i>0 )
        {
            sum+=aib[i];
            i-=(i&-i);
        }

        return sum;
    }

} tree;

int cb(int x)
{
    int st=1, dr=n, rez=1;

    while ( st<=dr )
    {
        int mij=(st+dr)/2;
        int nr=tree.query(mij);

        if ( nr>=x )
        {
            rez=mij;
            dr=mij-1;
        }
        else st=mij+1;
    }

    return rez;
}

int main()
{
    f >> n >> k;

    for (int i=1; i<=n; i++ )
        tree.update(i,1);

    // cautam cea mai mica permutare de n cu k inversiuni
    for (int i=1; i<=n; i++ ) // la pos i, cautam cea mai mica val pe care o putem pune
    {
        int nrinv_min=max(0,k-((n-i)*(n-i-1)/2)); // comb(n-i,2)

        // deci tb sa avem cel putin nrinv_min numere mai mici ca elementul de pe pozitia noastra
        // asa ca vom cauta al nrinv_min+1 element ramas (care este si cel mai mic posibil)

        int val=cb(nrinv_min+1);
        g << val << " ";

        tree.update(val,-1);
        k-=nrinv_min;
    }
    return 0;
}