Cod sursa(job #2507070)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 9 decembrie 2019 16:22:53
Problema Farfurii Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include<fstream>
#define N  100005
using namespace std;
ifstream fin("farfurii.in");
ofstream fout("farfurii.out");

//nr max de inversiuni care urm dupa o poz i este (n-i)(n-i+1)/2

long long n, tac;
long long sol[N];
bool viz[N];

void solve()
{
    long long i,x,inv,j,trebuie;
    for(i=1;i<=n;++i)
        if(((n-1-i)*(n-i))/2>tac)
        {
            //punem cel mai mic elem
            sol[i]=i;
            viz[i]=1;
        }
        else
        {
            //trb sa punem un elem mai mare ca sa apara inversiuni
            x=n-i+1;


            inv=((n+1-i)*(n-i))/2;

            trebuie=((n-1-i)*(n-i))/2;

            /*while(inv!=trebuie)x--,inv--;
            cout<<x;
            break;*/
            sol[i]=x;viz[x]=1;
            j=i+1;x=n;
            while(j<=n)
            {
                cout<<x<<" "<<viz[x]<<"\n";
                while(viz[x]==1)x--;
                sol[j++]=x;viz[x]=1;
                x--;
            }
            break;
        }
        for(i=1;i<=n;++i)fout<<sol[i]<<" ";
}

int main()
{
    fin>>n>>tac;
    solve();
    return 0;
}