Submission #976262

#	Time	Username	Problem	Language	Result	Execution time	Memory
976262		Unforgettablepl	Permutation (APIO22_perm)	C++17	91.33 / 100	3 ms	600 KiB

perm

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

std::vector<int32_t> construct_permutation(long long k){
    vector<int32_t> ans;
    if(k&1){
        ans.emplace_back(-1);
        k--;
    }
    for(int bit=1;bit<=64 and k;bit++) {
        ans.emplace_back(bit-1);
        if (k & (1ll << bit)){
            ans.emplace_back(-1);
            k -= (1ll << bit);
        }
    }
    ans.erase(--ans.end());
    int curr = ans.back();
    reverse(ans.begin(), ans.end());
    for(int32_t &i:ans)if(i==-1)i=++curr;
    reverse(ans.begin(), ans.end());
    return ans;
}

//static long long MX=1e18;
//
//static bool check_permutation(vector<int32_t> v)
//{
//    sort(v.begin(),v.end());
//    for(int32_t i=0;i<v.size();i++)
//        if(v[i]!=i) return 0;
//    return 1;
//}
//
//long long count_increasing(const vector<int32_t>& v) {
//    vector<long long> dp(v.size() + 1, 0);
//    dp[0] = 1;
//    for (int32_t x : v)
//    {
//        for (int32_t i = 0; i <= x; i++)
//        {
//            dp[x+1] += dp[i];
//            dp[x+1] = min(dp[x+1],MX+1);
//        }
//    }
//    long long result = 0;
//    for (int32_t i = 0; i <= (int32_t)v.size(); i++){
//        result += dp[i];
//        result = min(result,MX+1);
//    }
//    return result;
//}
//
//int32_t main() {
//    int32_t t;
//    assert(1 == scanf("%d", &t));
//    while(t--)
//    {
//        long long k;
//        assert(1 == scanf("%lld",&k));
//        vector<int32_t> ret=construct_permutation(k);
//        if(!check_permutation(ret))
//        {
//            printf("WA: Returned array is not a permutation\n");
//            exit(0);
//        }
//        long long inc=count_increasing(ret);
//        if(inc!=k)
//        {
//            if(inc==MX+1)
//                printf("WA: Expected %lld increasing subsequences, found more than %lld\n",k, MX);
//            else
//                printf("WA: Expected %lld increasing subsequences, found %lld\n",k,inc);
//            exit(0);
//        }
//        printf("%d\n",(int32_t)ret.size());
//        for(int32_t i=0;i<ret.size();i++)
//        {
//            printf("%d",ret[i]);
//            if(i+1==ret.size())
//                printf("\n");
//            else
//                printf(" ");
//        }
//    }
//    return 0;
//}

• Subtask 1: 10 / 10
• Subtask 2: 81.333333333 / 90