萌新初学OI,求调 TLE on test 4
查看原帖
萌新初学OI,求调 TLE on test 4
1221384
QwQ_lopgov_QwQ楼主2024/6/11 19:54
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
//#include <bits/stdc++.h>
#include <stdio.h>
#include <queue>
//#define int long long
#define swap(x, y) x ^= y ^= x ^= y

//using namespace std;
const int N = 4005;
int n, cnt0, cnt1, m, l, r, flag;
char S[N], T[N];
char s[N], t[N];
std::queue < int > ans;
int s0[N], t0[N];
int s1[N], t1[N];
bool is;
inline void reverse(int x)
{
	ans.push(x + x);
	l = 1, r = x;
	while (l < r)
	{
		swap(s[l], s[r]);
		l++, r--;
	}
	for (int i = 1; i <= x; i++)
	{
		if (s[i] > 0 && s[i] < 3) s[i] ^= 3;
	}
}
inline void Reverse(int x)
{
	l = 1, r = x;
	while (l < r)
	{
		swap(t[l], t[r]);
	}
	for (int i = 1; i <= x; i++)
	{
		if (t[i] > 0 && t[i] < 3) t[i] ^= 3;
	}
}
inline void ___()
{
	//cin >> S + 1;
	scanf("%s", S + 1);
	//n = strlen(S + 1);
	n = 1;
	while (S[n + 1] != '\0') n++;
	m = n / 2;
	cnt0 = cnt1 = 0;
	for (int i = 1; i <= m; i++)
	{
		s[i] = (S[(i << 1) - 1] ^ 48) << 1 | (S[i << 1] ^ 48);
		if (s[i] == 0) cnt0++;
		if (s[i] == 3) cnt1++;
	}
	//cin >> T + 1;
	scanf("%s", T + 1);
	for (int i = 1; i <= m; i++)
	{
		t[i] = (T[(i << 1) - 1] ^ 48) << 1 | (T[i << 1] ^ 48);
		if (t[i] == 0) cnt0--;
		if (t[i] == 3) cnt1--;
	}
	for (int i = 1; i <= m; i++)
	{
		s0[i] = s0[i - 1] + (s[i] == 1);
		s1[i] = s1[i - 1] + (s[i] == 2);
		t0[i] = t0[i - 1] + (t[i] == 1);
		t1[i] = t1[i - 1] + (t[i] == 2);
	}
	if (cnt0 || cnt1) return void(puts("-1"));
	flag = 0;
	if (t0[m] != s0[m])
	{
		for (int i = 1; i <= m; i++)
		{
			if (s0[m] == t0[m] - t0[i] + t1[i])
			{
				flag = i;
				Reverse(i);
				break;
			}
			if (t0[m] == s0[m] - s0[i] + s1[i])
			{
				reverse(i);
				break;
			}
			if (s0[m] - s0[i] + s1[i] == t0[m] - t0[i] + t1[i])
			{
				flag = i;
				Reverse(i);
				reverse(i);
				break;
			}
		}
	}
//	for (int i = 1; i <= m; i++) cout << (int)t[i] << ' '; cout << endl;
	for (int i = 1; i <= m; i++)
	{
//		for (int i = 1; i <= m; i++) cout << (int)s[i] << ' '; cout << endl;
		for (int j = i; j <= m; j++)
		{
			if (s[j] == t[i])
			{
//				cout << i << ' ' << j << endl;
				if (j > 1) reverse(j - 1);
				reverse(j);
				break;
			}
		}
	}
	reverse(m);
	if (flag) reverse(flag);
	//cout << ans.size() << endl;
	printf("%d\n", ans.size());
	//while (!ans.empty()) cout << ans.front() << ' ', ans.pop(); cout << endl;
	while (!ans.empty()) printf("%d ", ans.front()), ans.pop(); puts("");
}
/*
* 00 11 01 01 10
* 
* 10 01 10 00 11
* 11
* 2 6 8 8 10 4 6 6 8 8 10
*/
#define Multiple_Test 1




signed main()
{
	//ios::sync_with_stdio(false), cin.tie(), cout.tie();
	int T = 1;
#if Multiple_Test
	//cin >> T;
	scanf("%d", &T);
#endif
	while (T--) ___();
}

2024/6/11 19:54
加载中...