oj.uz

Submission #1020277

# Submission time Handle Problem Language Result Execution time Memory
1020277 2024-07-11T19:13:22 Z TAhmed33 Permutation (APIO22_perm) C++17
100 / 100
 2 ms 644 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 644 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 2 ms 500 KB Output is correct