Cod sursa(job #3315224)

Utilizator Lex._.Lex Guiman Lex._. Data 13 octombrie 2025 09:21:41
Problema Farfurii Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.15 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

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

int aint[NMAX*8]; ///pentru fiecare interval din aint, salvam cate dintre elementele din el nu au fost afisate pana acum

void build(int nod, int st, int dr) ///construire aint
{
    if(st==dr)
    {
        aint[nod]=1;
        return;
    }
    int mij=st+(dr-st)/2;
    build(nod*2, st, mij);
    build(nod*2+1, mij+1, dr);

    aint[nod]=aint[nod*2]+aint[nod*2+1];
}

void update(int poz, int nod, int st, int dr) ///update aint
{
    if(st==dr)
    {
        aint[nod]=0; ///marcam ca elementul a fost afisat
        return;
    }
    int mij=st+(dr-st)/2;
    if(poz<=mij) update(poz, nod*2, st, mij);
    else update(poz, nod*2+1, mij+1, dr);

    aint[nod]=aint[nod*2]+aint[nod*2+1];
}

int query(int nr, int nod, int st, int dr) ///cautam a nr-a valoare care nu a fost afisata pana acum
{
    if(aint[nod]<=nr)
    {
        return aint[nod];
    }
    int mij=st+(dr-st)/2;
    if(nr<aint[nod*2]) ///daca pozitia ceruta se gaseste in intervalul [st, mij]
    {
        return query(nr, nod*2, st, mij);
    }
    else ///daca pozitia ceruta se afla in intervalul [mij+1, dr]
    {
        return (mij-st+1)+query(nr-aint[nod*2], nod*2+1, mij+1, dr);
    }
}

int main()
{
    ///practic trebuie sa gasim sirul minim lexicografic care are k inversiuni
    ///solutie O(nlog(n)) cu aint
    long long n, k;
    in >> n >> k;
    build(1, 1, n);
    for(int i=1; i<=n; i++) ///vom cauta cea mai mica valoare care poate fi pusa pe pozitia i
    {
        int nr_inversiuni=max(k-(n-i)*(n-i-1)/2, (long long)0); ///numarul minim de inversiuni pe care trebuie sa le aiba elementul de pe pozitia i cu elementele de dupa
        int val=query(nr_inversiuni, 1, 1, n); ///vom vrea al (nr_inversiuni+1)-lea cel mai mic numar care nu a fost pus pana acum (ca sa aiba cel putin nr_inversiuni inversiuni cu elementele de dupa el)
        out << val << " ";
        k-=nr_inversiuni; ///scadem inversiunile deja existente in sir
        update(val, 1, 1, n); ///actualizam aint-ul
    }

    return 0;
}