Submission #784303

#	Time	Username	Problem	Language	Result	Execution time	Memory
784303		Trunkty	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	595 ms	5492 KiB

cheerleaders

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,ans=2e18;
vector<int> vans;
int arr[500005],newarr[500005];
int vals[21][3];

void bigsplit(){
    for(int i=0;i<(1<<n);i++){
        newarr[i/2+((i%2)*(1<<n-1))] = arr[i];
    }
    for(int i=0;i<(1<<n);i++){
        arr[i] = newarr[i];
    }
}

vector<int> dnc(int l, int r, int j){
    if(l==r){
        return {arr[l]};
    }
    int mid = (l+r)/2;
    vector<int> a = dnc(l,mid,j+1), b = dnc(mid+1,r,j+1);
    vector<int> c;
    int pos=0;
    for(int i=0;i<a.size();i++){
        while(pos<b.size() and a[i]>b[pos]){
            c.push_back(b[pos]);
            pos++;
            vals[j][1] += a.size()-i;
        }
        c.push_back(a[i]);
    }
    while(pos<b.size()){
        c.push_back(b[pos]);
        pos++;
    }
    pos=0;
    for(int i=0;i<b.size();i++){
        while(pos<a.size() and b[i]>a[pos]){
            pos++;
            vals[j][2] += b.size()-i;
        }
    }
    return c;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0;i<(1<<n);i++){
        cin >> arr[i];
    }
    if(n==0){
        cout << 0 << "\n";
        cout << "\n";
        return 0;
    }
    for(int i=1;i<=n;i++){
        bigsplit();
        for(int j=0;j<=n-1;j++){
            vals[j][1] = 0;
            vals[j][2] = 0;
        }
        dnc(0,(1<<n)-1,0);
        int tot=0;
        for(int j=0;j<=n-1;j++){
            tot += min(vals[j][1],vals[j][2]);
        }
        if(tot<ans){
            ans = tot;
            vans.clear();
            for(int j=1;j<=i;j++){
                vans.push_back(2);
            }
            for(int j=n-1;j>=0;j--){
                vans.push_back(2);
                if(vals[j][1]>vals[j][2]){
                    vans.push_back(1);
                }
            }
        }
    }
    cout << ans << "\n";
    for(int i:vans){
        cout << i;
    }
    cout << "\n";
    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'void bigsplit()':
cheerleaders.cpp:13:32: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   13 |         newarr[i/2+((i%2)*(1<<n-1))] = arr[i];
      |                               ~^~
cheerleaders.cpp: In function 'std::vector<long long int> dnc(ll, ll, ll)':
cheerleaders.cpp:28:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<a.size();i++){
      |                 ~^~~~~~~~~
cheerleaders.cpp:29:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |         while(pos<b.size() and a[i]>b[pos]){
      |               ~~~^~~~~~~~~
cheerleaders.cpp:36:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while(pos<b.size()){
      |           ~~~^~~~~~~~~
cheerleaders.cpp:41:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<b.size();i++){
      |                 ~^~~~~~~~~
cheerleaders.cpp:42:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         while(pos<a.size() and b[i]>a[pos]){
      |               ~~~^~~~~~~~~

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