Pagini recente » Cod sursa (job #1467688) | Cod sursa (job #2747181)
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");
long long n,k;
int main()
{
fin>>n>>k;
//trebuie sa gasesc permutarea cu k inversiuni
if(k==0) //permutarea finala nu are nicio inversiune
{
for(int i=1; i<=n; ++i)
fout<<i<<" ";
return 0;
}
if(k==n*(n-1)/2) //permutarea finala are numar maxim de inversiuni deci sunt in ordine descrescatoare
{
for(int i=n; i>=1; --i)
fout<<i<<" ";
return 0;
}
//idee: plec de la permutarea identica: 1,2,...,n si o alterez cu swapuri ca sa obtin k inversiuni
//caut valoarea M minima astfel incat M(M-1)/2 >= k ca sa pot pastra niste elemente de la inceput "blocate"
long long M=1;
while(M*(M-1)/2 < k) M++;
//las primele n-M valori neschimbate, iar pe urmatoarele le pun in ordine descrescatoare, astfel obtinand M*(M-1)/2 inversiuni
// urmand sa fac swapuri ca sa aduc la k inversiuni
for(int i=1; i<=n-M; ++i)
fout<<i<<" ";
if(M*(M-1)/2==k) //nu mai trebuie sa fac niciun swap pentru ca sunt exact k inversiuni
for(int i=n; i>=n-M+1; --i)
fout<<i<<" ";
else
{
long long dif=M*(M-1)/2-k;
//in subsecventa n,n-1,....,n-M+1 din secventa finala mare (1,2,...,n-M,n,n-1,...n-dif,n-dif-1,...,n-M+1)ar trebui
//sa permut spre dreapta subsecventa n,n-1,...,n-dif (n-dif-1,...,n-M+1 raman blocate)
//adica sa dau swap mereu cu elementul din stanga pornind de la valoarea n-dif
//pentru a scadea inversiunile adaugate in plus si a pastra cea mai mica dpdv lexicografic permutare
//deci sa obtin in final (1,2,...,n-M,n-dif,n,n-1,...n-dif+1,n-dif-1,...,n-M+1)
fout<<n-dif<<" ";
for(int i=n; i>=n-M+1; --i)
if(i!=n-dif)
fout<<i<<" ";
}
return 0;
}