# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
365766 | 2021-02-12T10:14:30 Z | jasen_penchev | Cheerleaders (info1cup20_cheerleaders) | C++14 | 1220 ms | 7388 KB |
#include <algorithm> #include <iostream> #include <utility> #include <string> #include <vector> #define endl '\n' using namespace std; const int MAXN = 17; int N; int a[(1ll << MAXN) + 5]; int b[(1ll << MAXN) + 5]; long long cnt1[MAXN + 5], cnt2[MAXN + 5]; void rec(int l, int r, int depth, vector< pair<int, int> > v) { if (r - l == 1) return; int mid = (l + r) / 2; vector< pair<int, int> > v1, v2; for (int i = 0; i < v.size(); ++ i) { if (v[i].second < mid) v1.push_back(v[i]); else v2.push_back(v[i]); } int pos = 0; for (int i = 0; i < v2.size(); ++ i) { while (pos < v1.size() and v1[pos].first < v2[i].first) pos++; cnt1[depth] += pos; cnt2[depth] += (mid - l) - pos; } rec(l, mid, depth + 1, v1); rec(mid, r, depth + 1, v2); } void split() { for (int i = 0; i < (1ll << N); ++ i) { if (i % 2 == 0) b[i / 2] = a[i]; else b[i / 2 + (1ll << (N - 1))] = a[i]; } for (int i = 0; i < (1ll << N); ++ i) { a[i] = b[i]; } } int main() { ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 0; i < (1ll << N); ++ i) { cin >> a[i]; } long long answer_inv = (long long)(1e18); if (N == 0) answer_inv = 0; string answer_moves = ""; for (int i = 0; i < N; ++ i) { vector< pair<int, int> > v; for (int j = 0; j < (1ll << N); ++ j) { v.push_back(make_pair(a[j], j)); } sort(v.begin(), v.end()); for (int j = 0; j < N; ++ j) { cnt1[j] = 0; cnt2[j] = 0; } rec(0, (1ll << N), 0, v); long long sum = 0; for (int j = 0; j < N; ++ j) { sum += min(cnt1[j], cnt2[j]); } if (answer_inv > sum) { answer_inv = sum; answer_moves = ""; for (int j = 0; j < i; ++ j) answer_moves += '2'; for (int j = 0; j < N; ++ j) { answer_moves += '2'; if (cnt1[N - 1 - j] < cnt2[N - 1 - j]) answer_moves += '1'; } } split(); } cout << answer_inv << endl; cout << answer_moves << endl; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct! |
2 | Correct | 1 ms | 364 KB | Correct! |
3 | Correct | 1 ms | 364 KB | Correct! |
4 | Correct | 1 ms | 364 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Correct! |
2 | Correct | 1 ms | 364 KB | Correct! |
3 | Correct | 1 ms | 364 KB | Correct! |
4 | Correct | 1 ms | 364 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 492 KB | Correct! |
2 | Correct | 9 ms | 492 KB | Correct! |
3 | Correct | 10 ms | 492 KB | Correct! |
4 | Correct | 9 ms | 492 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 174 ms | 2132 KB | Correct! |
2 | Correct | 170 ms | 2220 KB | Correct! |
3 | Correct | 365 ms | 3940 KB | Correct! |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 784 ms | 7296 KB | Correct! |
2 | Correct | 808 ms | 7336 KB | Correct! |
3 | Correct | 1220 ms | 7344 KB | Correct! |
4 | Correct | 1182 ms | 7336 KB | Correct! |
5 | Correct | 1145 ms | 7388 KB | Correct! |