Cod sursa(job #2531113)

Utilizator MirunaStefaniaLupascu Miruna-Stefania MirunaStefania Data 25 ianuarie 2020 18:14:37
Problema Farfurii Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include<fstream>
#define N 200005
using namespace std;

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

int a[N];

int n,m;
//1 2 3 4 5 6 7
//1 2 7 6 5 4 3 ->n*(n-1)/2 inversiuni-->ne va da n=5
//1 2 5 7 6 4 3 --> trebuie sa scapam de 10-8=2 inverisiuni

void print()
{
    int i;
    for(i=1;i<=n;++i)
        fout<<a[i]<<" ";
}

int main()
{
    int i,sum,x,poz;

    fin>>n>>m;
    i=1;
    while(i*(i-1)/2<=m)
        i++;

    sum=i;
    //inversam ultimele sum caractere
    for(i=1;i<=n-sum;++i)
        a[i]=i;
    x = n;
    poz = n - sum + 1;//de unde incep sa fie descrescatoare(7)
    for(i=n-sum+1;i<=n;++i)
        a[i]=x--;

    //print();

    sum = sum * (sum - 1) / 2;//nr curent de inversiuni(10)


    if(sum > m)//trebuie sa schimbam iar ultimul 10-8
    {
        sum = sum - m;//de cate inversiuni trebuie sa scap
        //il mut la stanga pe elem de pe la sum la poz
        sum=sum + poz;//de la ce poz trebuie sa il iau
        for(i = sum; i > poz; --i)
            swap(a[i],a[i-1]);

    }


    print();

    return 0;
}