Cod sursa(job #2107681)

Utilizator MaligMamaliga cu smantana Malig Data 17 ianuarie 2018 17:14:21
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<bitset>
#include<cstring>
#include<queue>

#define ull unsigned long long
#define ll long long
#define pb push_back
#define FOR(a,b,c) for (ll a=b;a<=c; ++a)
#define ROF(a,b,c) for (ll a=b;a>=c; --a)

using namespace std;
ifstream in("farfurii.in");
ofstream out("farfurii.out");

ll N,K;

ll inversiuni(ll);

int main()
{
    in>>N>>K;

    // solutia va fi de tipul 1 2 3 4 .... i-1 i j N N-1 N-2 .... i+1

    // determin indicele pentru care incepe modificarea vectorului;
    int i = 1;
    while (i <= N && inversiuni(i+1) >= K) {
        out<<i<<' ';

        ++i;
    }

    if (i <= N) {
        // used e generat in mod unic de necesitatea de a avea K inversiuni si sirul sa fie minim lexicografic;
        int used = i + (K - inversiuni(i+1));

        out<<used<<' ';

        for (int j = N;j >= i;--j) {
            if (j == used) {
                continue;
            }

            out<<j<<' ';
        }
    }

    in.close();out.close();
    return 0;
}

inline ll inversiuni(ll x) { // calculez numarul maxim de inversiuni de la dreapta lui x
    ll nr=N-x+1;
    return nr*(nr-1)/2;
}