Submission #576272

#	Time	Username	Problem	Language	Result	Execution time	Memory
576272		lunchbox	Permutation (APIO22_perm)	C++17	100 / 100	3 ms	340 KiB

perm

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

template<class T> using vec = vector<T>;

vec<long long> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541};

vec<int> get(long long k) {
    if (k <= 3) {
        vec<int> x(k - 1);
        iota(x.begin(), x.end(), 0);
        reverse(x.begin(), x.end());
        return x;
    }
    
    for (long long p : primes)
        if (k % p == 0 && k > p) {
            vec<int> x = get(k / p), y = get(p);
            int n = x.size();
            for (int v : y)
                x.push_back(n + v);
            return x;
        }

    if (k & 1) {
        vec<int> x = get(k - 1);
        for (int &v : x)
            v++;
        x.push_back(0);
        return x;
    } else {
        vec<int> x = get(k / 2);
        x.push_back(x.size());
        return x;
    }
}

vec<int> construct_permutation(long long k) {
    return get(k);
}

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