Pagini recente » Cod sursa (job #3306294) | Cod sursa (job #2423905) | Cod sursa (job #2328099) | Cod sursa (job #504241) | Cod sursa (job #3315201)
#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;
}