# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
579803 | 2022-06-19T22:28:14 Z | peuch | Permutation (APIO22_perm) | C++17 | 1000 ms | 340 KB |
#include "perm.h" #include<bits/stdc++.h> using namespace std; unordered_map<long long, vector<int> > dp; std::vector<int> construct_permutation(long long k) { if(k == 1) return vector<int> (0); if(k == 2) return vector<int> (1); if(!dp[k].empty()) return dp[k]; // printf("%lld\n", k); for(long long i = sqrt(k) + 1; i > 1; i--){ if(!dp[k].empty()) break; if(k % i != 0) continue; // printf("Testing dividing %lld by %d\n", k, i); vector<int> aux1 = construct_permutation(i); vector<int> aux2 = construct_permutation(k / i); if(dp[k].empty() || aux1.size() + aux2.size() < dp[k].size()){ dp[k].clear(); for(int i = 0; i < aux1.size(); i++) dp[k].push_back(aux1[i]); for(int i = 0; i < aux2.size(); i++) dp[k].push_back(aux2[i] + aux1.size()); } } // printf("Ok\n"); if(dp[k].empty()){ dp[k] = construct_permutation(k - 1); dp[k].insert(dp[k].begin(), dp[k].size()); } // printf("%lld\n", k); return dp[k]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 8 ms | 340 KB | Output is correct |
5 | Execution timed out | 1094 ms | 212 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |