Submission #1020277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020277		TAhmed33	Permutation (APIO22_perm)	C++17	100 / 100	2 ms	644 KiB

perm

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector <int> construct_permutation (ll k) {
    if (k == 1) {
        return {};
    }
    if (k == 2) {
        return {0};
    }
    if (k == 3) {
        return {1, 0};
    }
    auto g = construct_permutation(k / 4);
    if (k % 4 == 0) {
        g.push_back(int(g.size()));
        g.push_back(int(g.size()));
        return g;
    }
    if (k % 4 == 1) {
        g.push_back(int(g.size()));
        g.push_back(int(g.size()));
        g.push_back(-1);
        for (auto &i : g) i++;
        return g;
    }
    if (k % 4 == 2) {
        g.push_back(int(g.size()));
        g.push_back(-1);
        g.push_back(int(g.size()) - 1);
        for (auto &i : g) i++;
        return g;
    }
    int pos0 = -1, pos1 = -1;
    for (int i = 0; i < int(g.size()); i++) {
        if (g[i] == 1) {
            pos1 = i;
        }
        if (g[i] == 0) {
            pos0 = i;
        }
    }
    if (pos1 != -1 && pos0 != -1 && pos1 < pos0) {
        g.push_back(int(g.size()));
        g.push_back(int(g.size()));
        for (auto &i : g) {
            if (i >= 2) i++;
        }
        g.push_back(2);
        return g;
    }
    g.push_back(int(g.size()));
    g.push_back(-1);
    g.push_back(int(g.size()) - 1);
    g.push_back(-2);
    for (auto &i : g) i += 2;
    return g;
}
void print (int n) {
    auto g = construct_permutation(n);
    for (auto k : g) cout << k << " ";
    cout << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 90 / 90