Submission #1212296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212296		jasonic	Permutation (APIO22_perm)	C++20	86.63 / 100	2 ms	584 KiB

perm

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

using namespace std;
#define ll long long

int mn, mx;

void pushMin(vector<int> &vec) {
    vec.push_back(mn);
    if(mn == mx) {
        mx++;
    }
    mn--;
}

void pushMax(vector<int> &vec, int cnt) {
    for(int i = cnt+mx-1; i >= mx; i--) {
        vec.push_back(i);
    }
    if(mn == mx) {
        mn--;
    }
    mx += cnt;
}

vector<int> solve(ll k) {
    vector<int> res;
    if(k == 2) {
        pushMin(res);
    } else if (k != 1) {
        for(auto prime : {41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2}) {
            if(k % prime == 0) {
                res = solve(k/prime);
                pushMax(res, prime-1);
                return res;
            }
        }
        res = solve(k-1);
        pushMin(res);
    }
    return res;
}

vector<int> construct_permutation(ll k) {
    mn = 0, mx = 0;

    vector<int> res = solve(k);
    int mn = 0;
    for(auto &i : res) mn = min(mn, i);
    for(auto &i : res) i -= mn;

    return res;
}

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