Submission #987411

#	Time	Username	Problem	Language	Result	Execution time	Memory
987411		user736482	Cheerleaders (info1cup20_cheerleaders)	C++17	0 / 100	140 ms	4168 KiB

cheerleaders

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

pair<string,int> solve(vector<int>v2,vector<int>v3){
    string odp="";
    int 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)v3.size();j++){
            int smth = v3[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);
        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;
        v4.push_back(b);
    }
    for(int i=0;i<n+1;i++){
        resak.clear();
        for(int j=0;j<i;j++)
            resak.push_back('2');
        
        pair<string,int>ak=solve(v,v4);
       // 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]<<" ";
    //    }
        v5=v4;
        for(int j=0;j<(int)v.size();j++){
            bool smth=v[j]%2;
            v[j]=v[j]>>1;
            v[j]+=smth<<n-1;
            smth=j%2;
            int c=j;
            c=c>>1;
            v5[c+(smth<<n-1)]=v4[j];
        }
        v4=v5;
        //cout<<"\n";
    }
    cout<<mini<<"\n"<<res;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, int> solve(std::vector<int>, std::vector<int>)':
cheerleaders.cpp:12:22: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   12 |         int licz[1<<i+1];
      |                     ~^~
cheerleaders.cpp:13:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   13 |         for(int j=0;j<1<<i+1;j++)
      |                          ~^~
cheerleaders.cpp:17:34: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   17 |             int smth = v3[j]>>n-i-1;
      |                               ~~~^~
cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:68:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   68 |             v[j]+=smth<<n-1;
      |                         ~^~
cheerleaders.cpp:72:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   72 |             v5[c+(smth<<n-1)]=v4[j];
      |                         ~^~

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