제출 #276966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
276966		thebes	Cheerleaders (info1cup20_cheerleaders)	C++14	54 / 100	1619 ms	3064 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]; 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;
}

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=N-1;j>=0;j--){
                    if(dif[j]>0) sna += '1';
                    sna += '2';
                }
            }
            for(j=1;j<=(1<<N);j++){
                int lb = (p[j]-1)&1;
                p[j] = lb*(1<<(N-1))+((p[j]-1)>>1)+1;
            }
        }
        printf("%lld\n%s\n",ans,sna.c_str());
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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