Submission #1223001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223001		omsincoconut	Permutation (APIO22_perm)	C++17	89.82 / 100	524 ms	14736 KiB

perm

#include "perm.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

namespace {
    long long count_increasing_user(const vector<int>& v) {
        static long long MX=1e18;
        vector<long long> dp(v.size() + 1, 0);
        dp[0] = 1;
        for (int x : v)
        {
            for (int i = 0; i <= x; i++)
            {
                dp[x+1] += dp[i];
                dp[x+1] = min(dp[x+1],MX+1);
            }
        }
        long long result = 0;
        for (int i = 0; i <= (int)v.size(); i++){
            result += dp[i];
            result = min(result,MX+1);
        }
        return result;
    }

    bool first_execution = true;

    const int MAX_PERMSIZE = 9, MAX_PREPERM = (1<<MAX_PERMSIZE);
    vector<bool> found(MAX_PREPERM+20);
    vector<pair<ll, vector<int>>> perm_precomputed;
    vector<vector<int>> access_perm(MAX_PREPERM+20);

    const int MAX_PRETO = 1215640;
    vector<int> dp_value(MAX_PRETO+20, (int)1e9);
    vector<pair<int, int>> dp_backtrack(MAX_PRETO+20, {-1, -1}); // 0 = +, 1 = x

    void init() {
        for (int sz = 1; sz <= MAX_PERMSIZE; sz++) {
            vector<int> p(sz);
            iota(p.begin(), p.end(), 0);

            do {
                ll val = count_increasing_user(p);
                if (!found[val]) {
                    perm_precomputed.emplace_back(val, p);
                    found[val] = true;
                }
            } while (next_permutation(p.begin(), p.end()));
        }

        sort(perm_precomputed.begin(), perm_precomputed.end());
        for (auto [val, arr] : perm_precomputed)
            access_perm[val] = arr;

        dp_value[1] = 1;
        for (int i = 2; i < MAX_PRETO+5; i++) {
            for (int j = 0; j < perm_precomputed.size(); j++) {
                int val = perm_precomputed[j].first;
                int sz = perm_precomputed[j].second.size();

                if (val > i) break;
                if (i-val+1 != 1 && dp_value[i-val+1] + sz < dp_value[i]) {
                    dp_value[i] = dp_value[i-val+1] + sz;
                    dp_backtrack[i] = {0, val};
                }

                if (i%val == 0 && dp_value[i/val] + sz < dp_value[i]) {
                    dp_value[i] = dp_value[i/val] + sz;
                    dp_backtrack[i] = {1, val};
                }
            }
        }
    }
}

vector<int> add(vector<int> a, vector<int> b) {
    for (int &i : a) i += b.size();
    a.insert(a.end(), b.begin(), b.end());
    return a;
}

vector<int> multiply(vector<int> a, vector<int> b) {
    for (int &i : b) i += a.size();
    a.insert(a.end(), b.begin(), b.end());
    return a;
}

vector<int> construct_small(int k) {
    vector<int> cur = {};
    vector<pair<int, ll>> seq;
    while (k > 1) {
        auto [op, val] = dp_backtrack[k];
        if (op == 0) {
            seq.emplace_back(op, val);
            k -= val-1;
        } else {
            seq.emplace_back(op, val);
            k /= val;
        }
    }

    reverse(seq.begin(), seq.end());
    for (auto [op, val] : seq) {
        if (op == 0) {
            cur = add(cur, access_perm[val]);
            k -= val-1;
        } else {
            cur = multiply(cur, access_perm[val]);
            k /= val;
        }
    }

    return cur;
}

vector<int> construct_permutation(ll k) {
    if (first_execution) {
        init();
        first_execution = false;
    }

    ll v3 = k/MAX_PRETO/MAX_PRETO;
    ll v2 = (k-v3*MAX_PRETO*MAX_PRETO)/MAX_PRETO+(v3>0);
    ll v1 = (k-(v3*MAX_PRETO + v2 - (v3 > 0 && v2 > 0))*MAX_PRETO) + (v3 > 0 || v2 > 0);

    vector<int> cur;
    if (v3 > 0) {
        cur = construct_small(v3);
        cur = multiply(cur, construct_small(MAX_PRETO));
    }

    if (v2 > 0) {
        cur = add(cur, construct_small(v2));
    }

    if (v3 > 0 || v2 > 0) {
        cur = multiply(cur, construct_small(MAX_PRETO));
    }

    if (v1 > 0) {
        cur = add(cur, construct_small(v1));
    }

    return cur;
}

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