Cod sursa(job #2456404)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 14 septembrie 2019 11:48:41
Problema Farfurii Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 100001;

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

unsigned long long N, K;
unsigned long long v[NMAX];
vector < unsigned long long > I[NMAX];

void Read()
{
    fin >> N >> K;
}
void Do()
{
    int inv, nr;
    inv = 0;
    nr = 1;

    while( inv < K )
    {
        nr++;
        inv = ( nr * ( nr - 1 ) ) / 2;
        v[N - nr + 1] = nr - 1;
        I[nr-1].push_back( N - nr + 1 );
    }

    if( inv != K ) {v[ N - nr + 1] = inv - K; I[inv-K].push_back(N-nr+1); }

    int i, val;

    for( i = 1; i <= N - nr; ++i )
        v[i] = i;

    val = i;
    v[N] = val;
    for( i = N - 1; i > N - nr + 1; --i )
        {
            //cout <<v[i] << ' ' << I[v[i]].size() << ' ';
            if( I[v[i]].size() == 1 )
                v[i] = ++val;
            else
            {
                v[I[v[i]][1]] = ++val;
                v[I[v[i]][0]] = ++val;
            }

        }

    for( int i = 1; i <= N; ++i ) fout << v[i] << ' ';
}
int main()
{
    Read();
    Do();
    return 0;
}