Submission #1061413

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061413		stdfloat	Permutation (APIO22_perm)	C++17	91.33 / 100	2 ms	512 KiB

perm

#include <bits/stdc++.h>
#include "perm.h"
// #include "grader.cpp"
using namespace std;

using ll = long long;

vector<int> construct_permutation(ll k) {
    k--;

    map<ll, bool> m;
    queue<pair<ll, int>> q;
    q.push({k, 0});
    while (!q.empty()) {
        auto [x, tr] = q.front(); q.pop();

        if (x == 1) {
            int ln = 0, b = 0;
            while (x != k) {
                ln++;

                if (m[x]) x <<= 1;
                else b++;

                x++;
            }

            int a = b - 1;

            x = 1;
            vector<int> v = {b++};
            while (x != k) {
                if (m[x]) {
                    x <<= 1;
                    v.push_back(b++);
                }
                else {
                    v.push_back(a--);
                }

                x++;
            }
            
            return v;
        }

        if (!tr && m.find(x - 1) == m.end()) {
            m[x - 1] = 0;
            q.push({x - 1, 1});
        }
        if ((x & 1) && m.find((x - 1) >> 1) == m.end()) {
            m[(x - 1) >> 1] = 1;
            q.push({(x - 1) >> 1, 0});
        }
    }

    assert(false);
}

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