Submission #753126

#	Time	Username	Problem	Language	Result	Execution time	Memory
753126		DJeniUp	Cheerleaders (info1cup20_cheerleaders)	C++17	26 / 100	954 ms	2520 KiB

cheerleaders

#include "bits/stdc++.h"
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("O3")
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ll>pairld;
 
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
//#define MOD 998244353
#define INF 100000000000007
#define eps 0.0000000001
 
ll n,d[200],a[200],b[200];

vector<pairll>v;
 
int main(){
    
    cin>>n;
    if(n==0){
        cout<<0<<endl;
        return 0;
    }
    n=(1ll<<n);
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }
    ll res=INF;
    ll f=0;
    for(int i=1;i<=100000;i++){
        for(int j=1;j<=n;j++){
            if(j>n/2)a[j-n/2]=d[j];
            else a[j+n/2]=d[j];
            if(j%2==1){
                b[(j+1)/2]=d[j];
            }else b[j/2+n/2]=d[j];
        }
        
        ll x=0;
        ll y=0;
        for(int j=1;j<=n;j++){
            for(int k=j+1;k<=n;k++){
                if(a[j]>a[k])x++;
                if(b[j]>b[k])y++;
            }
            //if(i==1)cout<<b[j]<<" ";
        }
        //if(i==1)cout<<endl<<x<<" "<<y<<endl;
        if(rand()%2==1 || f==2){
            f=0;
            v.pb({2,y});
            res=min(res,y);
            swap(d,b);
        }else{
            f++;
            v.pb({1,x});
            res=min(res,x);
            swap(d,a);
        }
    }
    cout<<res<<endl;
    for(int i=0;i<v.size();i++){
        cout<<v[i].fr;
        if(v[i].sc==res)break;
    }
    cout<<endl;
 
    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

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