Sorting

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <climits>
#include <cstring>
#include <queue>

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using ii = pair<int,int>;
using vii = vector<pair<int,int>>;
using vb = vector<bool>;
template<typename T>
using Graph = vector<vector<T>>;

int ten[9] = 
{
	1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000
};

int digit(int n, int i)
{
	return (n / ten[i]) % 10;
}

int swap(int seq, int i, int j)
{
	if(j > i) swap(i, j);

	int d1 = digit(seq, i), d2 = digit(seq, i + 1);
	int d3 = digit(seq, j), d4 = digit(seq, j + 1);

	int res = seq / ten[i + 2];
	res = res * 10 + d4;
	res = res * 10 + d3;
	res = res * ten[i] + (seq % ten[i]);

	res = res / ten[j + 2];
	res = res * 10 + d2;
	res = res * 10 + d1;
	res = res * ten[j] + (seq % ten[j]);
	return res;
}

set<int> states;
void build()
{
	states.insert(1);
	for(int n = 2; n <= 8; ++n) 
	{
		int seq = 0;
		for(int i = 1; i <= n; ++i) 
		{
			seq = seq * 10 + i;
		}
		states.insert(seq);

		queue<int> q;
		q.push(seq);
		while(!q.empty())
		{
			int s = q.front();
			q.pop();

			for(int i = 0; i < n - 1; ++i)
			{
				for(int j = i + 2; j < n - 1; ++j) 
				{
					int t = swap(s, i, j);
					if(states.count(t) == 0)
					{
						states.insert(t);
						q.push(t);
					}
				}
			}
		}
	}
}

void solve()
{
	int n; cin >> n;
	int seq = 0;
	for(int i = 0; i < n; ++i)
	{
		int x; cin >> x;
		seq = seq * 10 + x;
	}

	if(states.count(seq)) cout << "YES\n";
	else cout << "NO\n";
}

int main () 
{
#ifdef LOCAL
   freopen("input.txt", "rt", stdin);
   freopen("output.txt", "wt", stdout);
#endif

   	ios_base::sync_with_stdio(false);
	cin.tie(0);

	build();
	int tc = 1; 
	cin >> tc;
	while(tc--) solve();
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: WRONG ANSWER

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED