oj.uz

답안 #753168

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753168 2023-06-04T16:48:44 Z DJeniUp Cheerleaders (info1cup20_cheerleaders) C++17
51 / 100
 1828 ms 2484 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<=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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Correct!
2 Correct 20 ms 668 KB Correct!
3 Correct 18 ms 676 KB Correct!
4 Correct 13 ms 596 KB Correct!

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 692 KB Correct!
2 Correct 107 ms 684 KB Correct!
3 Correct 105 ms 680 KB Correct!
4 Correct 105 ms 676 KB Correct!

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1826 ms 776 KB Correct!
2 Correct 1828 ms 960 KB Correct!
3 Correct 1816 ms 1016 KB Correct!
4 Correct 1809 ms 932 KB Correct!

Subtask #4
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 1112 KB Correct number of inversions, wrong sequence of operations
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 2484 KB Wrong number of inversions
2 Halted 0 ms 0 KB -