oj.uz

Submission #753164

# Submission time Handle Problem Language Result Execution time Memory
753164 2023-06-04T16:47:18 Z DJeniUp Cheerleaders (info1cup20_cheerleaders) C++17
26 / 100
 2000 ms 2732 KB 
#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<=50000;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

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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Correct!
2 Correct 29 ms 848 KB Correct!
3 Correct 28 ms 928 KB Correct!
4 Correct 22 ms 884 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 904 KB Correct!
2 Correct 167 ms 840 KB Correct!
3 Correct 173 ms 900 KB Correct!
4 Correct 167 ms 920 KB Correct!

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2089 ms 968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1396 KB Correct number of inversions, wrong sequence of operations
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 2732 KB Wrong number of inversions
2 Halted 0 ms 0 KB -