oj.uz

Submission #276984

# Submission time Handle Problem Language Result Execution time Memory
276984 2020-08-20T22:55:11 Z thebes Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 1647 ms 2740 KB 
#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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Correct!
2 Correct 1 ms 1152 KB Correct!
3 Correct 1 ms 1152 KB Correct!
4 Correct 1 ms 1152 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Correct!
2 Correct 1 ms 1152 KB Correct!
3 Correct 1 ms 1152 KB Correct!
4 Correct 1 ms 1152 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1280 KB Correct!
2 Correct 9 ms 1152 KB Correct!
3 Correct 10 ms 1152 KB Correct!
4 Correct 12 ms 1152 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 1536 KB Correct!
2 Correct 218 ms 1912 KB Correct!
3 Correct 531 ms 2424 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 2740 KB Correct!
2 Correct 1523 ms 2688 KB Correct!
3 Correct 1603 ms 2688 KB Correct!
4 Correct 1647 ms 2680 KB Correct!
5 Correct 1599 ms 2688 KB Correct!