oj.uz

Submission #838273

# Submission time Handle Problem Language Result Execution time Memory
838273 2023-08-26T12:28:19 Z ngano_upat_na Permutation (APIO22_perm) C++17
91.3333 / 100
 3 ms 340 KB 
#include "bits/stdc++.h"
#include "perm.h"
using namespace std;
using ll = long long;

vector<int> construct_permutation(long long k) {
    ll n = k;
    vector<int> ans;
    if (n <= 90) {
        for (int i=n-2; i>=0; i--) {
            ans.push_back(i);
        }   
        return ans;
    }   
    ll main_cap = 0, index = 0;
    for (ll i=0; ; i++) {
        ll a = (1LL << i);
        if (a <= n) {
            main_cap = a;
            index = i;
        }   
        else {
            break;
        }   
    }   
    for (int i=0; i<=index-1; i++) {
        ans.push_back(i);
    }   
    int cur = index;
    n -= main_cap;
    
    while (true) {
        if (n == 0) {
            return ans;
        }   
        vector<int> A;
        main_cap = 0, index = 0;
        for (ll j=0; ; j++) {
            ll a = (1LL << j);
            if (a <= n) {
                main_cap = a;
                index = j;
            }   
            else {
                break;
            }   
        }   
        bool added = false;
        index--;
        for (auto &e:ans) {
            if (e > index) {
                if (!added) {
                    A.push_back(cur);
                    A.push_back(e);
                    added = true;
                }   
                else {
                    A.push_back(e);
                }   
            }   
            else {
                A.push_back(e);
            }   
        }   
        ans = A;
        cur++;
        n -= main_cap;
    }   
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

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