Submission #865945

#	Time	Username	Problem	Language	Result	Execution time	Memory
865945		Darren0724	Cheerleaders (info1cup20_cheerleaders)	C++17	0 / 100	353 ms	6512 KiB

cheerleaders

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
#define ACorz ios_base::sync_with_stdio(false);cin.tie(0);
const int N=1<<17;
vector<int> a(N);
void f1(vector<int> &v){
    vector<int> g;
    int n=v.size();
    for(int i=0;i<n;i+=2){
        g.push_back(v[i]);
    }
    for(int i=1;i<n;i+=2){
        g.push_back(v[i]);
    }
    v=g;
}
void f2(vector<int> &v){
    vector<int> g;
    int n=v.size();
    for(int i=n/2;i<n;i++){
        g.push_back(v[i]);
    }
    for(int i=0;i<n/2;i++){
        g.push_back(v[i]);
    }
    v=g;
}
void print(vector<int> &v){
    for(int j:v){
        cout<<j<<' ';
    }
    cout<<endl;
}
struct BIT{
    vector<int> v=vector<int>(N+1);
    void add(int p){
        for(int i=p;i<=N;i+=i&(-i)){
            v[i]++;
        }
    }
    int ask(int p){
        int ans=0;
        for(int i=p;i>0;i-=i&(-i)){
            ans+=v[i];
        }
        return ans;
    }
};
int cal(vector<int> &v){
    int n=v.size();
    int ans=0;
    BIT b;
    for(int i=0;i<n;i++){
        ans+=b.ask(a[v[i]]);
        b.add(a[v[i]]);
    }
    return ans;
}

int32_t main(){
    ACorz;
    int m;cin>>m;
    int n=1<<m;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        v[i]=i;
        cin>>a[i];
        a[i]++;
    }
    vector<int> v1=v;
    int t=0;
    pair<int,int> ans={1e18,-1};
    while(1){
        f1(v1);
        t++;
        ans=min(ans,{cal(v1),t});
        f2(v1);
        t++;
        //print(v1);
        ans=min(ans,{cal(v1),t});
        if(v==v1){
            break;
        }
    }   
    //cout<<t<<endl; 
    cout<<ans.first<<endl;
    for(int i=0;i<ans.second;i++){
        cout<<(i&1)+1;
    }
    cout<<endl;
    return 0;
}
// 2:8
// 3:12

• Subtask 1: 0 / 16
• Subtask 2: 0 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 21
• Subtask 5: 0 / 28