# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
596676 | 2022-07-15T00:47:21 Z | slime | Permutation (APIO22_perm) | C++17 | 169 ms | 460 KB |
#include "perm.h" #include "bits/stdc++.h" using namespace std; static long long MX=1e18; long long count_increasing(const vector<int>& v) { vector<long long> dp(v.size() + 1, 0); dp[0] = 1; for (int x : v) { for (int i = 0; i <= x; i++) { dp[x+1] += dp[i]; dp[x+1] = min(dp[x+1],MX+1); } } long long result = 0; for (int i = 0; i <= (int)v.size(); i++){ result += dp[i]; result = min(result,MX+1); } return result; } int fastlog(long long x) { return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1); } std::vector<int> construct_permutation(long long k) { vector<int> cur = {}; cur.push_back(0); for(int i = 1; ; i++) { int lb = 0, rb = cur.size(); if(count_increasing(cur) == k) { return cur; } while(lb < rb) { int mid = (lb + rb + 1) >> 1; vector<int> now; for(int j=0; j<mid; j++) now.push_back(cur[j]); now.push_back(i); for(int j=mid; j<cur.size(); j++) now.push_back(cur[j]); if(count_increasing(now) <= k) lb = mid; else rb = mid - 1; } vector<int> now; for(int j=0; j<lb; j++) now.push_back(cur[j]); now.push_back(i); for(int j=lb; j<cur.size(); j++) now.push_back(cur[j]); cur = now; } return cur; } // 576460752303423487
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | 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 | Correct | 4 ms | 300 KB | Output is correct |
4 | Correct | 11 ms | 316 KB | Output is correct |
5 | Partially correct | 72 ms | 328 KB | Partially correct |
6 | Correct | 37 ms | 320 KB | Output is correct |
7 | Correct | 73 ms | 324 KB | Output is correct |
8 | Partially correct | 130 ms | 460 KB | Partially correct |
9 | Correct | 50 ms | 316 KB | Output is correct |
10 | Partially correct | 169 ms | 320 KB | Partially correct |
11 | Partially correct | 122 ms | 332 KB | Partially correct |
12 | Partially correct | 102 ms | 328 KB | Partially correct |
13 | Partially correct | 145 ms | 340 KB | Partially correct |