Submission #987424

#	Time	Username	Problem	Language	Result	Execution time	Memory
987424		user736482	Cheerleaders (info1cup20_cheerleaders)	C++17	72 / 100	128 ms	2640 KiB

cheerleaders

#include<bits/stdc++.h>
using namespace std;
int n,a,b,c;
long long mini=1000000000000000000;
string res,resak;
vector<int>v;
map<int,int>mp;

pair<string,long long> solve(vector<int>v2){
    string odp="";
    long long odpint=0;
    for(int i=0;i<n;i++){
        int licz[1<<i+1];
        for(int j=0;j<1<<i+1;j++)
            licz[j]=0;
        int wyn=0,wyn2=0;
        for(int j=0;j<(int)v2.size();j++){
            int smth = v2[j]>>n-i-1;
            if(smth%2==0)
                wyn+=licz[smth+1];
            if(smth%2==1)
                wyn2+=licz[smth-1];
            licz[smth]++;
        }
        //cout<<wyn<<" "<<wyn2<<"  ";
        if(wyn>wyn2){
            odp.push_back('1');
        }
        odpint+=min(wyn,wyn2);
        for(int j=1;j<n;j++)
            odp.push_back('2');
    }
   // v2={0,1,2,3};
    //cout<<"   ";
    //if(v==v2)
   //     return {"21",37};
   // return {"2137",2137};
   return {odp,odpint};
}
int main(){
    cin>>n;
    a=1<<n;
    for(int i=0;i<a;i++)
        v.push_back(0);
    for(int i=0;i<a;i++){
        cin>>b;
        v[b]=i;
    }
    for(int i=0;i<n+1;i++){
        resak.clear();
        for(int j=0;j<i;j++)
            resak.push_back('2');
        
        pair<string,long long>ak=solve(v);
        //cout<<ak.first<<"     ";
        if(ak.second<mini){
            res=resak;
            res+=ak.first;
            mini=ak.second;
        }
       // for(int j=0;j<(int)v.size();j++){
            //cout<<v[j]<<" ";
       // }
        for(int j=0;j<(int)v.size();j++){
            bool smth=v[j]%2;
            v[j]=v[j]>>1;
            v[j]+=smth<<n-1;
        }
        
        //cout<<"\n";
    }
    cout<<mini<<"\n"<<res;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, long long int> solve(std::vector<int>)':
cheerleaders.cpp:13:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   13 |         int licz[1<<i+1];
      |                     ~^~
cheerleaders.cpp:14:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   14 |         for(int j=0;j<1<<i+1;j++)
      |                          ~^~
cheerleaders.cpp:18:34: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   18 |             int smth = v2[j]>>n-i-1;
      |                               ~~~^~
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:67:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   67 |             v[j]+=smth<<n-1;
      |                         ~^~

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