oj.uz

Submission #753163

# Submission time Handle Problem Language Result Execution time Memory
753163 2023-06-04T16:46:24 Z DJeniUp Cheerleaders (info1cup20_cheerleaders) C++17
26 / 100
 1178 ms 2444 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<=20000;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 12 ms 660 KB Correct!
3 Correct 13 ms 684 KB Correct!
4 Correct 10 ms 596 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 692 KB Correct!
2 Correct 67 ms 668 KB Correct!
3 Correct 72 ms 672 KB Correct!
4 Correct 71 ms 580 KB Correct!

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1134 ms 696 KB Correct!
2 Incorrect 1178 ms 764 KB Wrong number of inversions
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1156 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 43 ms 2444 KB Wrong number of inversions
2 Halted 0 ms 0 KB -