Pagini recente » Cod sursa (job #1397002) | Cod sursa (job #532565) | Borderou de evaluare (job #1888793) | Cod sursa (job #1213093) | Cod sursa (job #3328328)
#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;
}