Cod sursa(job #2747173)

Utilizator DianaIfrosaIfrosa Diana DianaIfrosa Data 28 aprilie 2021 21:36:35
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int 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;
    }

    //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"

    int 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
    {
        int 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;
}