Submission #2225372


Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream &operator << (ostream& out,const pair<S,T>& o){
    out << "(" << o.first << "," << o.second << ")"; return out;
}

/*
<url:https://agc003.contest.atcoder.jp/tasks/agc003_c>
問題文============================================================
 高橋君は、誕生日に長さ N の数列をもらいました。i(1≦i≦N) 番目の要素は整数 Ai です。
 どの 2 つの要素も、互いに異なります。 高橋君はこの数列を単調増加になるように並べ替えたいです。
 高橋君は超能力者なので、以下の 2 つの操作が任意のタイミングでできます。
 
 操作1: 数列の連続する 2 つの要素を選び、その 2 つの順番を反転する。
 操作2: 数列の連続する 3 つの要素を選び、その 3 つの順番を反転する。

 高橋君は操作2は好きですが、操作1は嫌いです。
 この 2 種類の操作を使って数列を単調増加になるように並び替えるときの、操作1の最小回数を求めてください。

=================================================================

解説=============================================================
とりあえず、座圧したくなるからする[0-index]
 
 考察として
 操作1はある要素を基準とした時に,1回でその左右どちらの方向の全ての場所全てに到達可能
     (操作2の性質を組み合わせることによって 操作2 を複数回行い 操作1を1回行えば良い)
 
 操作2は ある要素を基準とした時に、その要素が偶数番目であれば偶数番目の全ての場所に移動可能
                             その要素が奇数番目であれば奇数番目の全ての場所に移動可能
 
 となる
 
 よって、例えば
 ex.サンプル1
 2 4 3 1
 (座圧)
     偶数番だが奇数番目に存在する
       v
 1 3 2 0
 ^
 奇数番だが、偶数番目に存在する
 
 となっており,1 を O 1 O O もしくは 0 を 0 O O O とするには
 必ず1回は操作1を行わなければならない
 ここで、 0 と 1 を交換しておけば 全ての偶(奇)数番号が 偶(奇)数番目に存在することになり
 単調増加に並べ替えることができる
 
 さらに、偶数番が奇数番目存在する個数と奇数番が偶数番に存在する個数は互いに一致するので
 
 どちらか一方の個数が、そのまま答えとなる
 
================================================================
*/
ll solve(){
    ll res = 0;
    ll N; cin >> N;
    vector<ll> A(N); for(auto&in:A) cin >> in;
    vector<ll> B = A;
    sort(B.begin(),B.end());
    for(int i = 0; i < N;i++){
        A[i] = lower_bound(B.begin(),B.end(),A[i]) - B.begin();
    }
    for(int i = 0; i < N;i+=2){
        if(A[i]%2 == 0) continue;
        res++;
    }
    return res;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    cout << solve() << endl;
	return 0;
}

Submission Info

Submission Time
Task C - BBuBBBlesort!
User clavis1107
Language C++14 (GCC 5.4.1)
Score 600
Code Size 3249 Byte
Status AC
Exec Time 29 ms
Memory 1792 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 2
AC × 24
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 29 ms 1792 KB
02.txt AC 29 ms 1792 KB
03.txt AC 29 ms 1792 KB
04.txt AC 29 ms 1792 KB
05.txt AC 27 ms 1792 KB
06.txt AC 27 ms 1792 KB
07.txt AC 27 ms 1792 KB
08.txt AC 16 ms 1792 KB
09.txt AC 16 ms 1792 KB
10.txt AC 15 ms 1792 KB
11.txt AC 15 ms 1792 KB
12.txt AC 15 ms 1792 KB
13.txt AC 16 ms 1792 KB
14.txt AC 27 ms 1792 KB
15.txt AC 27 ms 1792 KB
16.txt AC 27 ms 1792 KB
17.txt AC 27 ms 1792 KB
18.txt AC 1 ms 256 KB
19.txt AC 1 ms 256 KB
20.txt AC 1 ms 256 KB
21.txt AC 1 ms 256 KB
22.txt AC 1 ms 256 KB
s1.txt AC 1 ms 256 KB
s2.txt AC 1 ms 256 KB