Submission #88942

#TimeUsernameProblemLanguageResultExecution timeMemory
88942shoemakerjoBoard (CEOI13_board)C++14
100 / 100
7 ms2764 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long 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; } ll getval(vector<int>& cur) { if (cur.size() > 19) { return 1000000000; } ll ans = 0; for (int i = 0; i < cur.size(); i++) { ans *= 2LL; ans += cur[i] + 0LL; } 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; fn.push_back(1); sn.push_back(1); fsub.push_back(0); ssub.push_back(0); ll ans = 1000000000; 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; // cout << endl; ll cans = 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); } ll cdiff = 0LL; for (int i = 0; i < fn.size() && cdiff <= 300000; i++) { cdiff *= 2LL; cdiff += fn[i] - sn[i]; ll trav = (fn.size() - i - 1) * 2; ans = min(ans, trav + cdiff + cans); } cout << ans << endl; } //DIFFERENCE IS ALL MESSED UP (STILL, BAH!)

Compilation message (stderr)

board.cpp: In function 'long long int getval(std::vector<int>&)':
board.cpp:58: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:68: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:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < fguy.length(); ++i) {
                  ~~^~~~~~~~~~~~~~~
board.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < sguy.length(); ++i) {
                  ~~^~~~~~~~~~~~~~~
board.cpp:163:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < fn.size(); i++) {
                  ~~^~~~~~~~~~~
board.cpp:176:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < fn.size() && cdiff <= 300000; i++) {
                  ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...