Submission #67876443

---

Source Code Expand

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define sz(a) ((int) (a).size())
#define vi vector < int > 
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
using ll = long long;
#if defined(LOCAL)
#include "debug.cpp"
#else
#define debug(x...) 0
#endif // LOCAL
using namespace std;

const int N = 2e5 + 5;
int n, a[N];

void Main() {
	cin >> n;
	L(i, 0, n - 1) cin >> a[i];
	map<array<int, 2>, int> now = {{{-1, -1}, 0}}, next;
	auto update = [&](array<int, 2> ind, int cost){
		next[ind] = min(next.count(ind) ? next[ind] : int(1e9), cost);
	};
	L(i, 0, n - 1){
		for(auto [cur, cost]:now){
			//debug(cur, cost);
			if(
				i < 2 or 
				cur == array<int, 2>{a[i-2], a[i-1]} or
				cur == array<int, 2>{a[i-3], a[i-1]} or
				cur == array<int, 2>{a[i-1], a[i-2]}
			){
				update({cur[1], a[i]}, cost + (cur[1] != a[i]));
				update({a[i], cur[1]}, cost - (cur[0] != cur[1]) + (cur[0] != a[i]) + (a[i] != cur[1]) + 1);
			}
		}
		swap(now, next);
		next.clear();
	}
	int ans = 1e9;
	for(auto [_, cost]:now) ans = min(ans, cost);
	cout << ans << endl;
}

signed main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
};

Submission Info

Judge Result