Submission #147941

#TimeUsernameProblemLanguageResultExecution timeMemory
147941lycBoard (CEOI13_board)C++14
100 / 100
7 ms1852 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<int, ii> iii; typedef pair<ii, int> ri3; #define mp make_pair #define pb push_back #define fi first #define sc second #define SZ(x) (int)(x).size() #define ALL(x) begin(x), end(x) #define REP(i, n) for (int i = 0; i < n; ++i) #define FOR(i, a, b) for (int i = a; i <= b; ++i) #define RFOR(i, a, b) for (int i = a; i >= b; --i) string parse(string S) { vector<int> carry = { 0 }; vector<int> T = { 1 }; for (auto& c : S) { switch (c) { case '1': T.push_back(0); carry.push_back(0); break; case '2': T.push_back(1); carry.push_back(0); break; case 'L': --carry.back(); break; case 'R': ++carry.back(); break; case 'U': int spill = floor((carry.back() + T.back()) / 2.0); T.pop_back(); carry.pop_back(); carry.back() += spill; break; } } //cout << "T: "; for (int x : T) { cout << x << " "; } cout << endl; //cout << "C: "; for (int x : carry) { cout << x << " "; } cout << endl; reverse(ALL(T)); reverse(ALL(carry)); FOR(i,0,SZ(T)-1) { int cur = (T[i] + carry[i] + (1<<20)) % 2; int spill = floor((T[i] + carry[i]) / 2.0); T[i] = cur; if (spill) { if (i == SZ(T)-1) T.push_back(0), carry.push_back(spill); else carry[i+1] += spill; } } //cout << "T: "; for (int x : T) { cout << x << " "; } cout << endl; //cout << "C: "; for (int x : carry) { cout << x << " "; } cout << endl; T.pop_back(); reverse(ALL(T)); string t = ""; for (auto& c : T) t += '0'+c; return t; } int main() { //freopen("in.txt", "r", stdin); ios::sync_with_stdio(false); cin.tie(0); string A, B; cin >> A >> B; A = parse(A), B = parse(B); int ans = 2e5+10; if (A > B) swap(A,B); //cout << A << " " << B << endl; int diff = 0; for (int l = 0; diff < ans && l < (int)min(A.length(),B.length()); ++l) { diff *= 2; diff += B[l]-A[l]; //cout << diff << " " << (int)A.length()-1-l << " " << (int)B.length()-1-l << endl; ans = min(ans, diff + (int)A.length()-1-l + (int)B.length()-1-l); } cout << ans << endl; }
#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...