Cod sursa(job #2428686)

Utilizator topala.andreiTopala Andrei topala.andrei Data 6 iunie 2019 01:32:55
Problema Farfurii Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
// Determinarea permutarii de lungime N cu K inversuri
// minima lexicografic O(N^2)
#include <iostream>
#include <fstream>
#define MAXN 100001
using namespace std;
ifstream f("farfurii.in");
ofstream g("farfurii.out");
int N, K, maxInv;
bool viz[MAXN] = {false};
// Gasirea al x-lea element care nu a fost folosit
int firstAvailable(int x) {
    for (int i = 1; i <= N; ++i) {
        if (viz[i] == false) {
            --x;
            if (x == 0) {
                viz[i] = true;
                return i;
            }
        }
    }
    return 0;
}
int main()
{
    f >> N >> K;
    for (int i = 1; i <= N; ++i) {
        maxInv = (N - i)*(N - i - 1) / 2;
        if (K <= maxInv) {
            g << firstAvailable(1) << ' ';
        } else {
            g << firstAvailable(K - maxInv + 1) << ' ';
            K = maxInv;
        }
    }
    return 0;
}