测试数据的第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;
}