#include<bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define _ pair<ll,string>
#define pii pair<int,int>
using namespace std;
const int N = (1 << 17), mod = 1e9 + 7; // !
int n, t[N], h[N], P[N];
vector<int> v[N];
void upd(int x, int val) {
++x;
for(x; x >= 1; x -= x & (-x)) t[x] += val;
}
int get(int x) {
++x;
int ans = 0;
for(x; x <= (1 << n); x += x & (-x)) ans += t[x];
return ans;
}
_ solve(int n) {
ll CN = 1e15;
string S = "";
for(int mx = 0; mx < n; mx++) {
ll cn = 0;
string s = "";
for(int i = 0; i <= mx; i++) {
for(int j = 0; j < (1 << n); j++) v[(P[j] & ((1 << (mx + 1)) - 1)) - (P[j] & ((1 << (i + 1)) - 1))].push_back(P[j]);
ll c1 = 0, c2 = 0, C = 0;
for(int j = 0; j < (1 << n); j++) {
vector<int> b[2];
for(int k = 0; k < v[j].size(); k++) {
b[(v[j][k] & (1 << i)) > 0].push_back(v[j][k]);
}
v[j].clear();
if(i == 0) {
for(int t = 0; t < 2; t++) {
for(int k = 0; k < b[t].size(); k++) {
C += get(b[t][k]);
upd(b[t][k], 1);
}
for(int k = 0; k < b[t].size(); k++) {
upd(b[t][k], -1);
}
}
}
int l = 0;
ll Xn = 0;
for(int k = 0; k < b[1].size(); k++) {
while(l < b[0].size() && h[b[0][l]] < h[b[1][k]]) ++l;
Xn += (int)b[0].size() - l;
}
c1 += Xn;
c2 += (ll)((int)b[1].size() * (int)b[0].size()) - Xn;
}
c1 += C; c2 += C;
if(c1 <= c2) cn += c1, s += '2';
else s += "21", cn += c2;
}
if(cn < CN) CN = cn, S = s;
}
return {CN, S};
}
bool cmp(int a, int b) {
return (h[a] < h[b]);
}
main(){
cin >> n;
vector<int> x;
for(int i = 0; i + 1 <= (1 << n); i++) {
cin >> h[i];
P[i] = i;
}
sort(P, P + (1 << n), cmp);
_ p = solve(n);
for(int i = 0; i < (1 << (n - 1)); i++) {
swap(h[i], h[i + (1 << (n - 1))]);
}
sort(P , P + (1 << n), cmp);
_ p2 = solve(n);
cout << min(p2.f, p.f) << endl;
if(p2.f < p.f) cout << 1 << p2.s;
else cout << p.s;
}
Compilation message
cheerleaders.cpp: In function 'void upd(int, int)':
cheerleaders.cpp:13:9: warning: statement has no effect [-Wunused-value]
13 | for(x; x >= 1; x -= x & (-x)) t[x] += val;
| ^
cheerleaders.cpp: In function 'int get(int)':
cheerleaders.cpp:18:9: warning: statement has no effect [-Wunused-value]
18 | for(x; x <= (1 << n); x += x & (-x)) ans += t[x];
| ^
cheerleaders.cpp: In function 'std::pair<long long int, std::__cxx11::basic_string<char> > solve(int)':
cheerleaders.cpp:32:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int k = 0; k < v[j].size(); k++) {
| ~~^~~~~~~~~~~~~
cheerleaders.cpp:38:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int k = 0; k < b[t].size(); k++) {
| ~~^~~~~~~~~~~~~
cheerleaders.cpp:42:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int k = 0; k < b[t].size(); k++) {
| ~~^~~~~~~~~~~~~
cheerleaders.cpp:50:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int k = 0; k < b[1].size(); k++) {
| ~~^~~~~~~~~~~~~
cheerleaders.cpp:51:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | while(l < b[0].size() && h[b[0][l]] < h[b[1][k]]) ++l;
| ~~^~~~~~~~~~~~~
cheerleaders.cpp: At global scope:
cheerleaders.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
69 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
3284 KB |
Wrong number of inversions |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3284 KB |
Correct! |
| 2 |
Correct |
2 ms |
3284 KB |
Correct! |
| 3 |
Incorrect |
2 ms |
3412 KB |
Wrong number of inversions |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
3540 KB |
Correct! |
| 2 |
Incorrect |
13 ms |
3524 KB |
Wrong number of inversions |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
185 ms |
8500 KB |
Correct! |
| 2 |
Incorrect |
184 ms |
8436 KB |
Wrong number of inversions |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1064 ms |
27748 KB |
Wrong number of inversions |
| 2 |
Halted |
0 ms |
0 KB |
- |
