# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
674547 | 2022-12-25T05:30:40 Z | QwertyPi | Cheerleaders (info1cup20_cheerleaders) | C++14 | 345 ms | 24536 KB |
#include <bits/stdc++.h> #define int long long using namespace std; vector<int> f1(vector<int> v){ vector<int> nv; int k = v.size() >> 1; for(int i = k; i < k * 2; i++){ nv.push_back(v[i]); } for(int i = 0; i < k; i++){ nv.push_back(v[i]); } return nv; } vector<int> f2(vector<int> v){ vector<int> nv; int k = v.size() >> 1; for(int i = 0; i < k; i++){ nv.push_back(v[i * 2]); } for(int i = 0; i < k; i++){ nv.push_back(v[i * 2 + 1]); } return nv; } void pr(vector<int> v){ for(auto i : v) cout << i << ' '; cout << endl; } void g(vector<int>& a, string s){ vector<int> v(a.begin(), a.end()); for(auto i : s){ if(i == '1'){ v = f1(v); }else if(i == '2'){ v = f2(v); } } cout << s << ": "; pr(v); } int dp[1 << 17]; int b[1 << 17]; int inv(vector<int>& a, int l, int m, int r){ int x = l, y = m; int id = l; int cnt = 0; while(x != m || y != r){ if(y == r || x != m && a[x] < a[y]) b[id++] = a[x++], cnt += y - m; else b[id++] = a[y++]; } for(int i = l; i < r; i++) a[i] = b[i]; return cnt; } int test(int n, vector<int> a, vector<int>& data){ int ans = 0; for(int j = 0; j < n; j++){ int c = 0; for(int l = 0; l < (1 << n); l += (1 << j + 1)){ c += inv(a, l, l + (1 << j), l + (1 << j + 1)); } if(c <= (1LL << n + j - 1) - c) data.push_back(0); else data.push_back(1); ans += min(c, (1LL << n + j - 1) - c); } return ans; } int mcost[17]; int32_t main(){ vector<int> a[17], d[17]; int n; cin >> n; if(n == 0) { cout << "0\n11\n"; return 0; } for(int i = 0; i < (1 << n); i++){ int v; cin >> v; a[0].push_back(v); } for(int i = 1; i < n; i++){ a[i] = f2(a[i - 1]); } for(int i = 0; i < n; i++){ mcost[i] = test(n, a[i], d[i]); } int midx = 0; for(int i = 1; i < n; i++){ if(mcost[i] < mcost[midx]){ midx = i; } } cout << mcost[midx] << endl; vector<int> cur(1 << n); for(int i = 0; i < (1 << n); i++){ cur[i] = a[midx][i]; } string ans = "11"; for(int i = 0; i < midx; i++) ans.push_back('2'), cur = f2(cur); for(int i = 0; i < n; i++){ if(d[midx][i]){ for(int j = 0; j < i + 1; j++) ans.push_back('2'), cur = f2(cur); ans.push_back('1'), cur = f1(cur); for(int j = i + 1; j < n; j++) ans.push_back('2'), cur = f2(cur); } } cout << ans << endl; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct! |
2 | Correct | 0 ms | 212 KB | Correct! |
3 | Correct | 0 ms | 212 KB | Correct! |
4 | Correct | 0 ms | 212 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Correct! |
2 | Correct | 0 ms | 212 KB | Correct! |
3 | Correct | 0 ms | 212 KB | Correct! |
4 | Correct | 0 ms | 212 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 468 KB | Correct! |
2 | Correct | 3 ms | 468 KB | Correct! |
3 | Correct | 3 ms | 468 KB | Correct! |
4 | Correct | 3 ms | 468 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 5772 KB | Correct! |
2 | Correct | 35 ms | 5780 KB | Correct! |
3 | Correct | 62 ms | 11844 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 183 ms | 24408 KB | Correct! |
2 | Correct | 195 ms | 24392 KB | Correct! |
3 | Correct | 301 ms | 24380 KB | Correct! |
4 | Correct | 345 ms | 24536 KB | Correct! |
5 | Correct | 299 ms | 24400 KB | Correct! |