1698F - Equal Reversal - CodeForces Solution

#include <bits/stdc++.h>
const int N = 500;
using namespace std;

int tt, n, a[N + 5], b[N + 5];

void read(int &x) {
	x = 0; int w = 1; char c = getchar(); for(; c < '0' || c > '9'; c = getchar()) if (c == '-') w = -1;
	for(; c <= '9' && c >= '0'; c = getchar()) x = x * 10 + c - '0'; x *= w;
}

#define pii pair<int, int>
vector<pii > ans[2];
multiset<pii > s, t;

int p[N + 5], q[N + 5];
void rev(int l, int r, int opt) {
	if (!opt) reverse(a + l, a + r + 1);
	else reverse(b + l, b + r + 1);
	ans[opt].emplace_back(l, r);
}
#define fi first
#define se second

int main() {
	// freopen("t.in", "r", stdin);
	read(tt);
	while(tt--) {
		read(n);
		ans[0].clear(); ans[1].clear();
		for(int i = 1; i <= n; ++i) read(a[i]);
		for(int i = 1; i <= n; ++i) read(b[i]);

		if (a[1] != b[1] || a[n] != b[n]) {
			puts("NO");
			continue;
		}
		s.clear(); t.clear();
		for(int i = 1; i < n; ++i) {
			s.insert(make_pair(min(a[i], a[i + 1]), max(a[i], a[i + 1])));
			t.insert(make_pair(min(b[i], b[i + 1]), max(b[i], b[i + 1])));
		}

		multiset<pii >::iterator it1 = s.begin(), it2 = t.begin();
		// cout << ((*it1).fi) << ' ' << ((*it2).fi) << endl;
			
		bool flag = 0;
		while(it1 != s.end() && it2 != t.end()) {
			// cout << ((*it1).fi) << ' ' << ((*it2).fi) << endl;

			if ((*it1) != (*it2)) {
				flag = 1;
				break;
			}
			it1++; it2++;
		}
		if (flag) {
			puts("NO");
			continue;
		}
		puts("YES");
		for(int i = 2; i <= n; ++i)
			if (a[i] != b[i]) {
				int flag = 0;
				for(int j = i + 2; j <= n; ++j)
					if (b[j] == a[i - 1] && b[j - 1] == a[i]) {
						flag = j;
						break;
					}
				// if (i == 2) cout << "d" << flag << endl;
				if (flag) {rev(i - 1, flag, 1); continue;}
				for(int j = i + 2; j <= n; ++j)
					if (a[j] == b[i - 1] && a[j - 1] == b[i]) {
						flag = j;
						break;
					}
				if (flag) {rev(i - 1, flag, 0); continue;}
				for(int i = 1; i <= n; ++i) p[i] = 0;
				for(int i = 1; i <= n; ++i) q[i] = 0;
				for(int j = i + 2; j <= n; ++j) {
					if (a[j] == a[i - 1]) p[a[j - 1]] = j;
					if (b[j] == a[i - 1]) q[b[j - 1]] = j;
				}
				for(int j = 1; j <= n; ++j)
					if (p[j] && q[j]) {

				rev(i - 1, p[j], 0); rev(i - 1, q[j], 1);
					break;
					}
			}
		printf("%d\n", ans[0].size() + ans[1].size());
		for(auto v : ans[0]) printf("%d %d\n", v.fi, v.se);
		reverse(ans[1].begin(), ans[1].end());
		for(auto v : ans[1]) printf("%d %d\n", v.fi, v.se);
	}
	return 0;
}