Submission #276984

#	Time	Username	Problem	Language	Result	Execution time	Memory
276984		thebes	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	1647 ms	2740 KiB

cheerleaders

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,ssse3,sse3,sse4,popcnt,avx,mmx,abm")
#include <bits/stdc++.h>
using namespace std;

const int MN = 2e5+5, LG = 18;
int N, i, j, arr[MN], bit[MN], p[MN], a[MN]; long long ans, dif[LG];
string sna;

inline void upd(int p,int v){for(;p<=(1<<N);p+=p&-p)bit[p]+=v;}
inline int qu(int p){int r=0;for(;p;p-=p&-p)r+=bit[p]; return r;}

void rec(int l,int r,int b){
    if(l^r){
        int m = (l+r)>>1;
        for(int i=l;i<=m;i++) upd(arr[p[i]],1);
        for(int i=m+1;i<=r;i++) dif[b]+=m-l+1-2*qu(arr[p[i]]);
        for(int i=l;i<=m;i++) upd(arr[p[i]],-1);
        rec(l,m,b-1), rec(m+1,r,b-1);
    }
}

inline long long solve(){
    memset(dif,0,sizeof(dif));
    long long inv = 0;
    for(int i=1;i<=(1<<N);i++){
        inv += i-1-qu(arr[p[i]]);
        upd(arr[p[i]],1);
    }
    memset(bit,0,sizeof(bit));
    rec(1,(1<<N),N-1);
    for(int i=0;i<N;i++)
        inv -= max(0LL,dif[i]);
    return inv;
}

inline int rot(int x){
    int lb = x&(1<<(N-1));
    return ((x^lb)<<1)+(lb?1:0);
}

int main(){
    scanf("%d",&N);
    for(i=1;i<=(1<<N);i++){
        scanf("%d",&arr[i]);
        p[i]=i; arr[i]++;
    }
    if(!N) printf("0\n\n");
    else{
        ans = 1LL<<60;
        for(i=0;i<N;i++){
            long long cur = solve();
            if(cur<ans){
                ans = cur;
                sna = "";
                for(j=0;j<=i;j++) sna += '2';
                for(j=0;j<N;j++){
                    if(dif[j]>=0) sna += '1';
                    if(j+1!=N) sna += '2';
                }
            }
            for(j=1;j<=(1<<N);j++)
                a[j] = p[j];
            for(j=1;j<=(1<<N);j++)
                p[j]=a[rot(j-1)+1];
        }
        printf("%lld\n%s\n",ans,sna.c_str());
    }
    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
cheerleaders.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~

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