Submission #753168

#	Time	Username	Problem	Language	Result	Execution time	Memory
753168		DJeniUp	Cheerleaders (info1cup20_cheerleaders)	C++17	51 / 100	1828 ms	2484 KiB

cheerleaders

#include "bits/stdc++.h"
#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
 
using namespace std;
 
typedef int 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 10007
//#define MOD 998244353
#define INF 1000000007
#define eps 0.0000000001
 
ll n,p[2*N];

vector<pairll>v;

vector<ll>d,a,b;

void A(ll x){
    x++;
    for(int i=x;i>0;i-=(i&-i)){
        p[i]++;
    }
    return ;
}

ll R(ll x){
    x++;
    ll res=0;
    for(int i=x;i<=n;i+=(i&-i)){
        res+=p[i];
    }
    return res;
}
 
int main(){
    
    cin>>n;
    if(n==0){
        cout<<0<<endl;
        return 0;
    }
    n=(1ll<<n);
    d.pb(0);
    a.pb(0);
    b.pb(0);
    for(int i=1;i<=n;i++){
        d.pb(0);
        a.pb(0);
        b.pb(0);
        cin>>d[i];
    }
    ll res=INF;
    ll f=0;
    for(int i=1;i<=32000;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];
            p[j]=0;
        }
        
        ll x=0;
        ll y=0;
        
        
        //if(i==1)cout<<endl<<x<<" "<<y<<endl;
        if((rand()%2)*(clock()%2)==0 || f==2){
            for(int j=1;j<=n;j++){
                y+=R(b[j]);
                A(b[j]);
                //if(i==1)cout<<b[j]<<" ";
            }
            f=0;
            v.pb({2,y});
            res=min(res,y);
            swap(d,b);
        }else{
            
            for(int j=1;j<=n;j++){
                x+=R(a[j]);
                A(a[j]);
                //if(i==1)cout<<b[j]<<" ";
            }
            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:105:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

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