B.Odd Swap Sort（Codeforces Round ＃771 (Div. 2)）

This time cf Can also write A~C,B Question hung up , So make up

Links to questions ：https://codeforces.com/contest/1638/problem/B

The question ：

Given length is n Array of

What can be done ： If a[i]+a[i+1] (1 <= i <= n) It's an odd number , You can swap(a[i],a[i+1])

Now I ask if you can operate through this ( No limit of times ) Change the original array into a completely ascending array

analysis ：

This question hangs

At first sight , This is a bubble sort with a condition added , Then it was written like this , The pre-test is over , But I didn't expect a total of 8 Group data , Only four groups were tested last night .....

The next analysis ：

The addition of numbers with the same parity must be even

That is to say, in the sub sequence of odd elements and even elements of the array , The relative position of elements cannot be changed , As for the even and odd numbers , Even if the size and position are wrong , They are all adjustable .

So the idea is to check whether the sub sequence of odd elements and even elements of the array are originally ordered

AC Code：

#include<bits/stdc++.h>
using namespace std;
int t,n,x;
void solve()
{
	bool ans = true;
	cin >>n;
	int ji,ou;
	ji = ou = -1;
	for(int i = 1; i <= n; i++){
		cin >>x;
		if(x & 1){
			if(x < ji) ans = false;
			else ji = x;
		}
		else{
			if(x < ou) ans = false;
			else ou = x;
		} 
	} 
	if(ans) cout <<"YES" <<endl;
	else cout <<"NO" <<endl;
}
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >>t;
	while(t--) solve();	
	return 0;
} 

I have to say that this question has last year ICPC Nanjing station C I feel it