oj.uz

Submission #576272

# Submission time Handle Problem Language Result Execution time Memory
576272 2022-06-12T21:26:27 Z lunchbox Permutation (APIO22_perm) C++17
100 / 100
 3 ms 340 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 3 ms 340 KB Output is correct
11 Correct 3 ms 340 KB Output is correct
12 Correct 3 ms 340 KB Output is correct
13 Correct 3 ms 340 KB Output is correct