#include <bits/stdc++.h>
using namespace std;
int arr[(1<<18)+5];
int curarr[(1<<18)+5];
vector<int> f1(vector<int> v){
vector<int> nw;
for (int x = 0; x<v.size(); x+=2){
nw.push_back(v[x]);
}
for (int x = 1; x<v.size(); x+=2){
nw.push_back(v[x]);
}
return nw;
}
int n,logn;
vector<long long> allvals(int lpos, int sz ,vector<pair<int,int> > sorted){
if (sorted.size()==1){
return {0};
}
// printf("called with sz %d, sortsz %d\n",sz,sorted.size());
long long inter1 = 0,inter2 = 0;
vector<pair<int,int> >sortl,sortr;
for (auto x : sorted){
if (x.second-lpos<sz/2) sortl.push_back(x);
else sortr.push_back(x);
}
vector<long long> ans;
long long c1 = 0;
for (auto x : sortr){
while (c1<sortl.size() && sortl[c1]<x) c1++;
inter2 += c1;
}
inter1 = ((long long)sortl.size()*(long long)(sortl.size()))-inter2;
// printf("inter = %lld %lld\n",inter1,inter2);
if (sortl.size()==1) return {inter1,inter2};
vector<long long> r1 = allvals(lpos,sz/2,sortl);
vector<long long> r2 = allvals(lpos+sz/2,sz/2,sortr);
for (int x = 0; x<sz/2; x++){
ans.push_back(r1[x]+r2[x]+inter1);
}
for (int x = 0; x<sz/2; x++){
ans.push_back(r1[x]+r2[x]+inter2);
}
return ans;
}
inline void scan(int &a){
a = 0;
char ch = ' ';
while (ch<'0' || ch>'9') ch = getchar();
while (ch>='0' && ch<='9'){
a = (a<<3)+(a<<1)+ch-'0';
ch = getchar();
}
}
set<pair<int,int> > vis;
vector<int> finpath;
int wantpos1 = -1;
int wantpos2 = -1;
bool dfs(int pos1, int pos2){
int cur = vis.size();
vis.insert({pos1,pos2});
if (vis.size()>cur){
// printf("vis %d %d\n",pos1,pos2);
if (pos1==wantpos1 && pos2==wantpos2) return true;
int t1 = pos1>=n/2?pos1-n/2:(pos1+n/2);
int t2 = pos2>=n/2?pos2-n/2:(pos2+n/2);
if (dfs(t1,t2)){
finpath.push_back(1);
return true;
}
t1 = (pos1&1)?(pos1/2+n/2):pos1/2;
t2 = (pos2&1)?(pos2/2+n/2):pos2/2;
if (dfs(t1,t2)){
finpath.push_back(2);
return true;
}
}
return false;
}
int main(){
//freopen("test.txt","r",stdin);
scan(n);
logn = n;
n = 1<<n;
if (n==1){
printf("0\n");
return 0;
}
vector<int> t;
for(int x = 0; x<n; x++){
scan(arr[x]);
t.push_back(arr[x]);
}
vector<pair<int,int> > sorted;
sorted.clear();
for (int x = 0; x<n; x++){
sorted.push_back({t[x],x});
}
sort(sorted.begin(),sorted.end());
long long ans = 999999999999999999LL;
int anspos;
int numlogn;
for (int x = 0; x<logn; x++){
for (int x2 = 0; x2<n; x2++){
curarr[x2] = t[x2];
}
auto res = allvals(0,n,sorted);
int c = 0;
for (auto x2 : res){
//printf("%d ",x2);
if (x2<ans){
ans= x2;
anspos = c;
numlogn = x;
}
c++;
//printf("%lld \n",x);
}
//printf("\n");
t = f1(t);
sorted.clear();
for (int x2 = 0; x2<n; x2++){
sorted.push_back({t[x2],x2});
}
sort(sorted.begin(),sorted.end());
}
for (int x = 0; x<numlogn; x++){
t = f1(t);
}
for (int x = 0; x<n; x++){
curarr[x] = t[x];
}
for (int x = 0; x<n; x++){
if (curarr[x]==arr[0]) wantpos1 = x;
if (curarr[x]==arr[1]) wantpos2 = x;
}
// printf("anspos = %d\n",anspos);
for (int x = logn-1; x>=0; x--){
if (anspos&(1<<x)){
wantpos1 ^= (1<<x);
wantpos2^=(1<<x);
}
}
// printf("wantpos = %d %d\n",wantpos1,wantpos2);
dfs(0,1);
printf("%lld\n",ans);
for (int x = finpath.size()-1; x>=0; x--){
printf("%d",finpath[x]);
}
}
Compilation message
cheerleaders.cpp: In function 'std::vector<int> f1(std::vector<int>)':
cheerleaders.cpp:9:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
9 | for (int x = 0; x<v.size(); x+=2){
| ~^~~~~~~~~
cheerleaders.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for (int x = 1; x<v.size(); x+=2){
| ~^~~~~~~~~
cheerleaders.cpp: In function 'std::vector<long long int> allvals(int, int, std::vector<std::pair<int, int> >)':
cheerleaders.cpp:34:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (c1<sortl.size() && sortl[c1]<x) c1++;
| ~~^~~~~~~~~~~~~
cheerleaders.cpp: In function 'bool dfs(int, int)':
cheerleaders.cpp:70:19: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
70 | if (vis.size()>cur){
| ~~~~~~~~~~^~~~
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:136:22: warning: 'numlogn' may be used uninitialized in this function [-Wmaybe-uninitialized]
136 | for (int x = 0; x<numlogn; x++){
| ~^~~~~~~~
cheerleaders.cpp:148:19: warning: 'anspos' may be used uninitialized in this function [-Wmaybe-uninitialized]
148 | if (anspos&(1<<x)){
| ~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Correct! |
| 2 |
Correct |
1 ms |
204 KB |
Correct! |
| 3 |
Correct |
1 ms |
204 KB |
Correct! |
| 4 |
Correct |
1 ms |
204 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Correct! |
| 2 |
Correct |
1 ms |
332 KB |
Correct! |
| 3 |
Correct |
1 ms |
292 KB |
Correct! |
| 4 |
Correct |
1 ms |
332 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
3140 KB |
Correct! |
| 2 |
Correct |
22 ms |
2804 KB |
Correct! |
| 3 |
Correct |
22 ms |
2896 KB |
Correct! |
| 4 |
Correct |
17 ms |
1612 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
379 ms |
23616 KB |
Correct! |
| 2 |
Correct |
292 ms |
15752 KB |
Correct! |
| 3 |
Correct |
565 ms |
17808 KB |
Correct! |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1519 ms |
64332 KB |
Correct! |
| 2 |
Correct |
1408 ms |
48312 KB |
Correct! |
| 3 |
Execution timed out |
2052 ms |
74772 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
