Cod sursa(job #3315201)

Utilizator Lex._.Lex Guiman Lex._. Data 12 octombrie 2025 22:24:53
Problema Farfurii Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

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

int n;
int aib[NMAX];

void update(int poz) ///marcam care elemente au fost afisate pana acum
{
    while(poz<=n)
    {
        aib[poz]++;
        poz+=(poz&(-poz));
    }
}

int cautare_binara(int val) ///cautam pozitia la al val-lea element care nu a fost afisat pana acum
{
    int putere_2=1;
    while(putere_2*2<=n) putere_2*=2; ///cea mai mare putere a lui 2 mai mica ca n
    int poz=0;
    while(putere_2>0)
    {
        if(poz+putere_2<=n)
        {
            if(putere_2-aib[poz+putere_2]<val)
            {
                val-=putere_2-aib[poz+putere_2];
                poz+=putere_2;
            }
        }
        putere_2/=2;
    }
    return poz+1;
}

int main()
{
    ///practic trebuie sa gasim sirul minim lexicografic care are k inversiuni
    ///solutie O(nlog(n)) cu aib
    long long k;
    in >> n >> k;
    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 poz=cautare_binara(nr_inversiuni+1); ///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 << poz << " ";
        k-=(long long)nr_inversiuni; ///scadem inversiunile deja existente in sir
        update(poz); ///actualizam aib-ul
    }

    return 0;
}