Submission #675422

#	Time	Username	Problem	Language	Result	Execution time	Memory
675422		hotboy2703	Cheerleaders (info1cup20_cheerleaders)	C++14	25 / 100	1034 ms	1852 KiB

cheerleaders

#include<bits/stdc++.h>
using namespace std;
#define BIT(mask,i) (((mask) >> (i)) & 1LL)
#define MASK(i) (1LL<<(i))
int h[200100];
int n;
int a[200100];
int BIT[(1<<17) + 5];
void update(int x,int val){
    for (;x<=(1<<17);x+=x&-x)BIT[x]+=val;
}
int get(int x){
    int res = 0;
    for (;x > 0;x -= x &-x)res += BIT[x];
    return res;
}
pair <long long,long long> solve(){
    long long res = 0;
    long long id = 0;
    for (int i = n - 1;i >= 0;i --){
        long long inversion = 0;
        for (int j = 0;j < (1<<(n-1-i));j ++){
            for (int k = 0;k < (1<<i);k ++){
                update(a[(j<<(i+1)) + (1<<i) + k] + 1,1);
            }
            for (int k = 0;k < (1<<i);k ++){
                inversion += get(a[(j<<(i+1)) + k]);
            }
            for (int k = 0;k < (1<<i);k ++){
                update(a[(j<<(i+1)) + (1<<i) + k] + 1,-1);
            }
        }
        if ((1<<(n-1+i)) - inversion < inversion){
            id ^= (1<<i);
        }
        res += min((1<<(n-1+i)) - inversion , inversion);
    }
    return {res,id};
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;
    for (int i = 0;i < (1<<n);i ++)cin>>h[i];
    long long ans = LLONG_MAX;
    pair <long long, long long> trace;
    for (int i = n - 1;i >= 0;i --){
        for (int mask = 0;mask < MASK(n);mask++){
            int cur = i;
            int real_mask = 0;
            for (int k = n - 1;k >= 0;k --){
                real_mask ^= (BIT(mask,k)<<cur);
                cur--;
                if (cur < 0)cur = n - 1;
            }
            a[mask] = h[real_mask];
        }
        pair <long long,long long> tmp = solve();
        if (tmp.first < ans){
            ans = tmp.first;
            trace.first = i;
            trace.second = tmp.second;
        }
    }
    cout<<ans<<'\n';
    for (int i = 0;i < n - 1 - trace.first;i++)cout<<2;
    for (int i = n - 1;i >= 0;i--){
        if (BIT(trace.second,i))cout<<1;
        cout<<2;
    }
    return 0;
}

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