oj.uz

Submission #573131

# Submission time Handle Problem Language Result Execution time Memory
573131 2022-06-06T03:56:35 Z dqhungdl Permutation (APIO22_perm) C++17
10 / 100
 1000 ms 340 KB 
#include "perm.h"
#include <bits/stdc++.h>
using namespace std;

int pivot;
vector<int> rs;

void backtrack(long long k) {
    if (!k)
        return;
    int 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 1 ms 212 KB Output is correct

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Partially correct 1 ms 340 KB Partially correct
4 Partially correct 1 ms 340 KB Partially correct
5 Execution timed out 1084 ms 212 KB Time limit exceeded
6 Halted 0 ms 0 KB -