# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
744078 | 2023-05-18T07:53:49 Z | veehz | Permutation (APIO22_perm) | C++17 | 13 ms | 340 KB |
#include "perm.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; void normalize(vector<float>& a) { vector<float> b = a; sort(b.begin(), b.end()); map<float, int> mp; for (int i = 0; i < (int)b.size(); i++) mp[b[i]] = i; for (int i = 0; i < (int)a.size(); i++) a[i] = mp[a[i]]; } void insert(vector<float>& a, int x) { int n = a.size(); if (x == 0) { a.push_back(n); a.push_back(n + 1); return; } else if (x == 1) { a.push_back(n); a.push_back(n + 1); a.push_back(-1); normalize(a); return; } else if (x == 2) { a.push_back(n); a.push_back(-1); a.push_back(n + 1); normalize(a); return; } else { // x = 3 bool oneThenZero; for (auto& i : a) { if (i == 1) { oneThenZero = true; break; } else if (i == 0) { oneThenZero = false; break; } } if (oneThenZero) { a.push_back(n); a.push_back(n + 1); a.push_back(1.5); normalize(a); return; } else { a.push_back(n); a.push_back(-1); a.push_back(n + 1); a.push_back(-2); normalize(a); return; } } } vector<int> construct_permutation(ll k) { vector<int> a; while (k) { a.push_back(k % 4); k /= 4; } reverse(a.begin(), a.end()); vector<float> ans; int nxt = 0; switch (a[0]) { case 1: break; case 2: ans.push_back(0); break; case 3: ans.push_back(1); ans.push_back(0); break; } for (int i = 1; i < (int)a.size(); i++) { insert(ans, a[i]); } vector<int> res(ans.begin(), ans.end()); return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 300 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 300 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 2 ms | 304 KB | Output is correct |
4 | Correct | 2 ms | 296 KB | Output is correct |
5 | Correct | 7 ms | 340 KB | Output is correct |
6 | Correct | 6 ms | 332 KB | Output is correct |
7 | Correct | 8 ms | 340 KB | Output is correct |
8 | Correct | 13 ms | 324 KB | Output is correct |
9 | Correct | 3 ms | 340 KB | Output is correct |
10 | Correct | 13 ms | 300 KB | Output is correct |
11 | Correct | 12 ms | 340 KB | Output is correct |
12 | Correct | 10 ms | 340 KB | Output is correct |
13 | Correct | 12 ms | 340 KB | Output is correct |