求助
查看原帖
求助
295509
你的洛楼主2023/8/10 13:15

测试数据的第72个点RE了,将测试数据下载后发现本地并没有RE,且答案正确(指m相同),求调

#include <iostream>
#include <deque>
#include <stack>
#include <vector>
using namespace std;
const int N = 5e5 + 5;
int n, m;
string s, t;
deque<pair<char, int> > q1, q2, p1, p2;
stack<pair<char, int> > t1, t2; // will connect to q1 and q2
vector<pair<int, int> > ans1, ans2;
inline void change (int c1, int c2, vector<pair<int, int> > &v) // represent the number blocks
{
	pair<char, int> tmp;
	int a = 0, b = 0;
	for (int i = 0; i < c1; ++i)
	{
		tmp = p1[0];
		p1.pop_front ();
		t2.push (tmp);
		a += tmp.second;
	}
	for (int i = 0; i < c2; ++i)
	{
		tmp = p2[0];
		p2.pop_front ();
		t1.push (tmp);
		b += tmp.second;
	}
	v.push_back ({a, b});
	for (int i = 0; i < c2; ++i)
	{
		tmp = t1.top ();
		t1.pop ();
		if (p1[0].first == tmp.first) {p1[0].second += tmp.second; continue;}
		p1.push_front (tmp);
	}
	for (int i = 0; i < c1; ++i)
	{
		tmp = t2.top ();
		t2.pop ();
		if (p2[0].first == tmp.first) {p2[0].second += tmp.second; continue;}
		p2.push_front (tmp);
	}
}
inline void printans ()
{
	cout << ans1.size () << endl;
	for (auto it : ans1)
		cout << it.first << " " << it.second << endl;
	exit (0);
}
inline void work (vector<pair<int, int> > &v)
{
	while (p1.size () > 1 || p2.size () > 1)
	{
		if (abs ((int) p1.size () - (int) p2.size ()) < 2 || (p1.size () <= 3 && p2.size () <= 3)) change (1, 1, v);
		else
		{
			if (p1.size () < p2.size ()) change (1, 3, v);
			else change (3, 1, v);
		}
	}
}
int main ()
{
#ifndef ONLINE_JUDGE
    freopen ("test.in", "r", stdin);
    freopen ("test.out", "w", stdout);
#endif
	ios::sync_with_stdio (0);
	cin >> s >> t;
	n = s.length ();
	m = t.length ();
	q1.push_back ({s[0], 0});
	for (int i = 0; i < n; ++i)
	{
		if (s[i] == q1[q1.size () - 1].first) q1[q1.size () - 1].second++;
		else q1.push_back ({s[i], 1});
	}
	q2.push_back ({t[0], 0});
	for (int i = 0; i < m; ++i)
	{
		if (t[i] == q2[q2.size () - 1].first) q2[q2.size () - 1].second++;
		else q2.push_back ({t[i], 1});
	}
	if (q1.size () == 1 && q2.size () == 1) printans ();
	if (q1[0].first != q2[0].first) p1 = q1, p2 = q2, work (ans1);
	else
	{
		if (q1.size () > 1)
		{
			p1 = q1, p2 = q2;
			change (1, 0, ans1);
			work (ans1);
		}
		else ans1.resize (N);
		if (q2.size () > 1)
		{
			p1 = q1, p2 = q2;
			change (0, 1, ans2);
			work (ans2);
		}
		else ans2.resize (N);
		if (ans1.size () > ans2.size ()) swap (ans1, ans2);
	}
	printans ();
	return 0;
}

2023/8/10 13:15
加载中...