// CF template, version 3.0
#include <bits/stdc++.h>
using namespace std;
#define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0)
#define getTest int t; cin >> t
#define eachTest for (int _var=0;_var<t;_var++)
#define get(name) int (name); cin >> (name)
#define out(o) cout << (o)
#define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
#define sortl(name) sort((name).begin(), (name).end())
#define rev(name) reverse((name).begin(), (name).end())
#define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
#define decision(b) if (b){out("YES");}else{out("NO");}
#define int long long
vector<int> compress(string s) {
stack<pair<int, int>> sst;
int n = s.size();
int len, el, lenbefore, bfbf;
forto(n, i) {
switch (s[i]) {
case '1':
if (sst.empty() || sst.top().first == 2) sst.push({1, 1});
else {
len = sst.top().second;
sst.pop();
sst.push({1, len + 1});
}
break;
case '2':
if (sst.empty() || sst.top().first == 1) sst.push({2, 1});
else {
len = sst.top().second;
sst.pop();
sst.push({2, len + 1});
}
break;
case 'U':
len = sst.top().second;
el = sst.top().first;
sst.pop();
if (len != 1) sst.push({el, len - 1});
break;
case 'L':
el = sst.top().first;
len = sst.top().second;
if (el == 2) {
sst.pop();
if (len != 1) {
sst.push({2, len - 1});
sst.push({1, 1});
} else {
if (sst.empty()) {
sst.push({1, 1});
} else {
lenbefore = sst.top().second;
sst.pop();
sst.push({1, lenbefore + 1});
}
}
} else {
sst.pop();
lenbefore = sst.top().second;
if (lenbefore != 1) {
sst.pop();
sst.push({2, lenbefore - 1});
sst.push({1, 1});
sst.push({2, len});
} else {
sst.pop();
if (sst.empty()) {
sst.push({1, 1});
sst.push({2, len});
} else {
bfbf = sst.top().second;
sst.pop();
sst.push({1, bfbf + 1});
sst.push({2, len});
}
}
}
break;
case 'R':
el = sst.top().first;
len = sst.top().second;
if (el == 1) {
sst.pop();
if (len != 1) {
sst.push({1, len - 1});
sst.push({2, 1});
} else {
if (sst.empty()) {
sst.push({2, 1});
} else {
lenbefore = sst.top().second;
sst.pop();
sst.push({2, lenbefore + 1});
}
}
} else {
sst.pop();
lenbefore = sst.top().second;
if (lenbefore != 1) {
sst.pop();
sst.push({1, lenbefore - 1});
sst.push({2, 1});
sst.push({1, len});
} else {
sst.pop();
if (sst.empty()) {
sst.push({2, 1});
sst.push({1, len});
} else {
bfbf = sst.top().second;
sst.pop();
sst.push({2, bfbf + 1});
sst.push({1, len});
}
}
}
break;
}
}
vector<int> res;
while (!sst.empty()) {
int ele = sst.top().first;
int leng = sst.top().second;
forto(leng, i) res.push_back(ele);
sst.pop();
}
rev(res);
return res;
}
signed main() {
improvePerformance;
//getTest;
//eachTest {
string s, t;
cin >> s;
cin >> t;
vector<int> S = compress(s);
vector<int> T = compress(t);
if (S > T) swap(S, T);
int slev = S.size();
int tlev = T.size();
vector<int> moves;
int cnt = 0;
forto(min(slev, tlev), i) {
if (S[i] == T[i]) cnt *= 2;
else if (S[i] == 1) cnt = cnt * 2 + 1;
else cnt = cnt * 2 - 1;
if (cnt > 250000) break;
moves.push_back(cnt);
}
int ans = slev + tlev;
forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
out(ans);
//}
}
Compilation message
board.cpp: In function 'std::vector<long long int> compress(std::string)':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
board.cpp:24:5: note: in expansion of macro 'forto'
24 | forto(n, i) {
| ^~~~~
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
board.cpp:132:9: note: in expansion of macro 'forto'
132 | forto(leng, i) res.push_back(ele);
| ^~~~~
board.cpp: In function 'int main()':
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
board.cpp:154:9: note: in expansion of macro 'forto'
154 | forto(min(slev, tlev), i) {
| ^~~~~
board.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ^
board.cpp:162:9: note: in expansion of macro 'forto'
162 | forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
| ^~~~~
board.cpp:15:52: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
| ~~~~~~^~~~~~~~
board.cpp:162:9: note: in expansion of macro 'forto'
162 | forto(moves.size(), i) ans = min(ans, slev - i + tlev - i + moves[i] - 2);
| ^~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
3 ms |
468 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
4 ms |
636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
468 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
252 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
5 ms |
596 KB |
Output is correct |
| 3 |
Correct |
3 ms |
540 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
1740 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
1 ms |
720 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
1652 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1740 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
1 ms |
588 KB |
Output is correct |
| 5 |
Correct |
5 ms |
2268 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
1740 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1868 KB |
Output is correct |
| 3 |
Correct |
4 ms |
2120 KB |
Output is correct |
| 4 |
Correct |
1 ms |
720 KB |
Output is correct |
| 5 |
Correct |
1 ms |
720 KB |
Output is correct |
| 6 |
Correct |
4 ms |
2240 KB |
Output is correct |
