#include <bits/stdc++.h>
using namespace std;
string fguy, sguy;
vector<int> fn, sn;
vector<int> fsub, ssub;
void inc(vector<int>& cur) {
for (int i = cur.size()-1; i >= 0; i--) {
if (cur[i] == 0) {
cur[i] = 1;
break;
}
else cur[i] = 0;
}
}
int getlast(vector<int>& cur) {
return cur[cur.size()-1];
}
vector<int> subvec(vector<int> a, vector<int> b) {
//returns a vector, assumes same length
bool hascarry = false;
for (int i = a.size()-1; i >= 0; i--) {
if (hascarry) {
a[i]--;
hascarry = false;
}
a[i] -= b[i];
if (a[i] < 0) {
a[i] += 2;
hascarry = true;
}
}
return a;
}
int getval(vector<int>& cur) {
if (cur.size() > 17) {
return 1000000000;
}
int ans = 0;
for (int i = 0; i < cur.size(); i++) {
ans *= 2;
ans += cur[i];
}
return ans;
}
string printvect(vector<int>& guy) {
string res = "";
for (int i = 0; i < guy.size(); i++) {
res += to_string(guy[i]);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> fguy >> sguy;
int cl = fguy.length();
fn.push_back(1);
sn.push_back(1);
fsub.push_back(0);
ssub.push_back(0);
int ans = 1000000000;
int nummoves = 0;
for (int i = 0; i < fguy.length(); ++i) {
if (fguy[i] == '1') {
fn.push_back(0);
fsub.push_back(0);
}
if (fguy[i] == '2') {
fn.push_back(1);
fsub.push_back(0);
}
if (fguy[i] == 'U') {
if (getlast(fsub) == 1) {
if (getlast(fn) != 1) {
inc(fsub);
}
}
fn.pop_back();
fsub.pop_back();
}
if (fguy[i] == 'L') {
inc(fsub);
}
if (fguy[i] == 'R') {
inc(fn);
}
}
for (int i = 0; i < sguy.length(); ++i) {
if (sguy[i] == '1') {
sn.push_back(0);
ssub.push_back(0);
}
if (sguy[i] == '2') {
sn.push_back(1);
ssub.push_back(0);
}
if (sguy[i] == 'U') {
if (getlast(ssub) == 1) {
if (getlast(sn) != 1) {
inc(ssub);
}
}
sn.pop_back();
ssub.pop_back();
}
if (sguy[i] == 'L') {
inc(ssub);
}
if (sguy[i] == 'R') {
inc(sn);
}
}
fn = subvec(fn, fsub);
sn = subvec(sn, ssub);
// cout << "fn: " << printvect(fn) << " " << getval(fn) << endl;
// cout << "sn: " << printvect(sn) << " " << getval(sn) << endl;
int cans = 0;
int cdiff = 0;
while (fn.size() > sn.size()) {
fn.pop_back();
cans++;
}
while (sn.size() > fn.size()) {
sn.pop_back();
cans++;
}
bool sngreater = false;
for (int i = 0; i < fn.size(); i++) {
if (fn[i] > sn[i]) break;
if (sn[i] > fn[i]) {
sngreater = true;
break;
}
}
if (sngreater) {
fn.swap(sn);
}
vector<int> dt = subvec(fn, sn);
vector<int> diff;
for (int i = 0; i < dt.size(); i++) {
if (dt[i] == 0) {
for (int j = i+1; j < dt.size(); j++) {
diff.push_back(dt[j]);
}
break;
}
}
for (int i = fn.size()-1; i >= 0; i--) {
ans = min(ans, cans + getval(diff));
if (diff.size()) diff.pop_back();
cans += 2;
}
cout << ans << endl;
}
Compilation message
board.cpp: In function 'int getval(std::vector<int>&)':
board.cpp:57:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < cur.size(); i++) {
~~^~~~~~~~~~~~
board.cpp: In function 'std::__cxx11::string printvect(std::vector<int>&)':
board.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < guy.size(); i++) {
~~^~~~~~~~~~~~
board.cpp: In function 'int main()':
board.cpp:92:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < fguy.length(); ++i) {
~~^~~~~~~~~~~~~~~
board.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < sguy.length(); ++i) {
~~^~~~~~~~~~~~~~~
board.cpp:165:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < fn.size(); i++) {
~~^~~~~~~~~~~
board.cpp:179:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < dt.size(); i++) {
~~^~~~~~~~~~~
board.cpp:181:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i+1; j < dt.size(); j++) {
~~^~~~~~~~~~~
board.cpp:80:6: warning: unused variable 'cl' [-Wunused-variable]
int cl = fguy.length();
^~
board.cpp:90:6: warning: unused variable 'nummoves' [-Wunused-variable]
int nummoves = 0;
^~~~~~~~
board.cpp:152:6: warning: unused variable 'cdiff' [-Wunused-variable]
int cdiff = 0;
^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
720 KB |
Output is correct |
| 2 |
Correct |
6 ms |
876 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
876 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2316 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2448 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
2448 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
2536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
2536 KB |
Output is correct |
| 2 |
Correct |
6 ms |
2904 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
2904 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
