oj.uz

Submission #573133

# Submission time Handle Problem Language Result Execution time Memory
573133 2022-06-06T03:57:51 Z dqhungdl Permutation (APIO22_perm) C++17
71.2154 / 100
 12 ms 1108 KB 
#include "perm.h"
#include <bits/stdc++.h>
using namespace std;

int pivot;
vector<int> rs;

void backtrack(long long k) {
    if (!k)
        return;
    long long pw2 = 1, cnt = 0;
    while (pw2 * 2 - 1 <= k) {
        pw2 *= 2;
        cnt++;
    }
    for (int i = pivot - cnt + 1; i <= pivot; i++)
        rs.push_back(i);
    pivot -= cnt;
    backtrack(k - pw2 + 1);
}

std::vector<int> construct_permutation(long long k) {
    pivot = 1e9;
    rs.clear();
    backtrack(k - 1);
    int minVal = *min_element(rs.begin(), rs.end());
//    cout << minVal << '\n';
//    for (int &x: rs)
//        cout << x << ' ';
//    cout << '\n';
    for (int &x: rs)
        x -= minVal;
    return rs;
}

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
61.215384618 / 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 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 2 ms 340 KB Partially correct
5 Partially correct 5 ms 468 KB Partially correct
6 Partially correct 5 ms 556 KB Partially correct
7 Partially correct 8 ms 680 KB Partially correct
8 Partially correct 10 ms 980 KB Partially correct
9 Correct 1 ms 340 KB Output is correct
10 Partially correct 12 ms 1108 KB Partially correct
11 Partially correct 11 ms 844 KB Partially correct
12 Partially correct 9 ms 852 KB Partially correct
13 Partially correct 9 ms 852 KB Partially correct