oj.uz

Submission #918495

# Submission time Handle Problem Language Result Execution time Memory
918495 2024-01-30T00:33:07 Z tuannm Permutation (APIO22_perm) C++17
71.2154 / 100
 74 ms 1180 KB 
#include<bits/stdc++.h>
#include "perm.h"
#define pb push_back
using namespace std;

vector<int> construct_permutation(long long k){
    vector<int> ans;
    for(long long N = k; N <= k + 100; ++N){
        if(N % 2 != 0)
            continue;
        multiset<int> tmp;
        vector<int> v;
        for(int i = 1; (1LL << i) <= N; ++i){
            if(N & (1LL << i))
                tmp.insert(i);
        }
        if((int)tmp.size() > N - k + 1)
            continue;
        bool ok = true;
        while((int)tmp.size() < N - k + 1){
            auto it = tmp.lower_bound(2);
            if(it == tmp.end()){
                ok = false;
                break;
            }
            tmp.erase(it);
            int add = *it - 1;
            tmp.insert(add);
            tmp.insert(add);
        }
        if(!ok)
            continue;
        int m = 0;
        for(auto i : tmp)
            m += i;
        for(auto i : tmp){
            vector<int> tttt;
            for(int j = 1; j <= i; ++j)
                tttt.pb(--m);
            reverse(tttt.begin(), tttt.end());
            for(auto j : tttt)
                v.pb(j);
        }
        if(ans.empty() || (int)ans.size() > (int)v.size())
            ans = v;
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 19 ms 448 KB Output is correct

Subtask #2
61.215384618 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 19 ms 448 KB Output is correct
3 Partially correct 39 ms 444 KB Partially correct
4 Partially correct 40 ms 344 KB Partially correct
5 Partially correct 52 ms 596 KB Partially correct
6 Partially correct 64 ms 484 KB Partially correct
7 Partially correct 56 ms 860 KB Partially correct
8 Partially correct 67 ms 896 KB Partially correct
9 Correct 48 ms 708 KB Output is correct
10 Partially correct 63 ms 1180 KB Partially correct
11 Partially correct 61 ms 852 KB Partially correct
12 Partially correct 57 ms 848 KB Partially correct
13 Partially correct 74 ms 848 KB Partially correct