Submission #1061412

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061412		stdfloat	Permutation (APIO22_perm)	C++17	91.33 / 100	2 ms	352 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--;
    ll remk = k;

    int sm = -1;
    vector<int> v;
    while (k) {
        int x = __lg(k + 1);

        sm += x;
        v.push_back(x);
        
        k -= (1LL << x) - 1;
    }

    if (sm < 90) {
        vector<int> ans;
        for (int i = 0; i < (int)v.size(); i++) {
            for (int j = sm - v[i] + 1; j <= sm; j++) {
                ans.push_back(j);
            }

            sm -= v[i];
        }

        return ans;
    }

    k = remk;

    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