Pagini recente » Cod sursa (job #3308503) | Cod sursa (job #1814232) | Monitorul de evaluare | Cod sursa (job #676484) | Cod sursa (job #3315224)
#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;
}