oj.uz

Submission #976262

# Submission time Handle Problem Language Result Execution time Memory
976262 2024-05-06T11:16:32 Z Unforgettablepl Permutation (APIO22_perm) C++17
91.3333 / 100
 3 ms 600 KB 
#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.0 / 10.0

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

Subtask #2
81.333333333 / 90.0

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