#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
using namespace std;
typedef int ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ll>pairld;
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 10007
//#define MOD 998244353
#define INF 1000000007
#define eps 0.0000000001
ll n,p[2*N];
vector<pairll>v;
vector<ll>d,a,b;
void A(ll x){
x++;
for(int i=x;i>0;i-=(i&-i)){
p[i]++;
}
return ;
}
ll R(ll x){
x++;
ll res=0;
for(int i=x;i<=n;i+=(i&-i)){
res+=p[i];
}
return res;
}
int main(){
cin>>n;
if(n==0){
cout<<0<<endl;
return 0;
}
n=(1ll<<n);
d.pb(0);
a.pb(0);
b.pb(0);
for(int i=1;i<=n;i++){
d.pb(0);
a.pb(0);
b.pb(0);
cin>>d[i];
}
ll res=INF;
ll f=0;
for(int i=1;i<=160000;i++){
for(int j=1;j<=n;j++){
if(j>n/2)a[j-n/2]=d[j];
else a[j+n/2]=d[j];
if(j%2==1){
b[(j+1)/2]=d[j];
}else b[j/2+n/2]=d[j];
p[j]=0;
}
ll x=0;
ll y=0;
//if(i==1)cout<<endl<<x<<" "<<y<<endl;
if((rand()%2)*(clock()%2)==0 || f==2){
for(int j=1;j<=n;j++){
y+=R(b[j]);
A(b[j]);
//if(i==1)cout<<b[j]<<" ";
}
f=0;
v.pb({2,y});
res=min(res,y);
swap(d,b);
}else{
for(int j=1;j<=n;j++){
x+=R(a[j]);
A(a[j]);
//if(i==1)cout<<b[j]<<" ";
}
f++;
v.pb({1,x});
res=min(res,x);
swap(d,a);
}
}
cout<<res<<endl;
for(int i=0;i<v.size();i++){
cout<<v[i].fr;
if(v[i].sc==res)break;
}
cout<<endl;
return 0;
}
Compilation message
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0;i<v.size();i++){
| ~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Correct! |
2 |
Correct |
91 ms |
2404 KB |
Correct! |
3 |
Correct |
92 ms |
2376 KB |
Correct! |
4 |
Correct |
67 ms |
2356 KB |
Correct! |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
276 ms |
2360 KB |
Correct! |
2 |
Correct |
526 ms |
2504 KB |
Correct! |
3 |
Correct |
523 ms |
2440 KB |
Correct! |
4 |
Correct |
518 ms |
2504 KB |
Correct! |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2051 ms |
1164 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
61 ms |
2864 KB |
Correct number of inversions, wrong sequence of operations |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
90 ms |
4108 KB |
Wrong number of inversions |
2 |
Halted |
0 ms |
0 KB |
- |