Submission #777277

#TimeUsernameProblemLanguageResultExecution timeMemory
777277NK_Board (CEOI13_board)C++17
100 / 100
102 ms3796 KiB
// Success consists of going from failure to failure without loss of enthusiasm #include <bits/stdc++.h> using namespace std; #define nl '\n' #define sz(x) int(x.size()) using str = string; using ll = long long; template<class T> using V = vector<T>; const int INF = int(1e9) + 10; const int DIF = 10; using T = array<int, 2>; const int nax = (1 << 17); T seg[2 * nax]; int lazy[2 * nax]; void push(int x, int L, int R) { lazy[x] %= 2; if (lazy[x] == 1) swap(seg[x][0], seg[x][1]); if (L != R) for(int i = 0; i < 2; i++) lazy[2*x+i] += lazy[x]; lazy[x] = 0; } void pull(int x) { seg[x] = T{seg[2*x][0] + seg[2*x+1][0], seg[2*x][1] + seg[2*x+1][1]}; } void flip(int l, int r, int x = 1, int L = 0, int R = nax - 1) { push(x, L, R); if (r < L || R < l) return; if (l <= L && R <= r) { lazy[x]++; push(x, L, R); return; } int M = (L + R) / 2; flip(l, r, 2*x, L, M); flip(l, r, 2*x+1, M+1, R); pull(x); } void upd(int p, T v, int x = 1, int L = 0, int R = nax - 1) { push(x, L, R); if (p < L || R < p) return; if (L == R) { seg[x] = v; return; } int M = (L + R) / 2; upd(p, v, 2*x, L, M); upd(p, v, 2*x+1, M+1, R); pull(x); } int find_last(int p, int x = 1, int L = 0, int R = nax - 1) { push(x, L, R); if (seg[x][p] == 0) return nax; if (L == R) return L; int M = (L + R) / 2; int res = find_last(p, 2*x+1, M+1, R); if (res != nax) return res; return find_last(p, 2*x, L, M); } int value(int p, int x = 1, int L = 0, int R = nax - 1) { push(x, L, R); if (L == R) { return seg[x][0] == 0; } int M = (L + R) / 2; if (p <= M) return value(p, 2*x, L, M); else return value(p, 2*x+1, M+1, R); } const T ONE = {0, 1}, ZER = {1, 0}, EMP = {0, 0}; int main() { cin.tie(0)->sync_with_stdio(0); for(int i = 0; i < 2 * nax; i++) { lazy[i] = 0; seg[i] = EMP; } str A, B; cin >> A >> B; int d = -1; auto add = [&](bool pos) { int c = (pos ? 0 : 1); int p = find_last(c); flip(p, d - 1); }; auto get = [&](str& S) { d = 0; for(auto& c : S) { if (isdigit(c)) upd(d++, c == '2' ? ONE : ZER); if (c == 'U') upd(--d, EMP); if (c == 'L') add(0); if (c == 'R') add(1); } S = "0"; for(int i = 0; i < d; i++) { S += char('0' + value(i)); upd(i, EMP); } }; get(A), get(B); int ans = INF; int xa = 0, xb = 0; bool aft = 0; for(int i = 0; i < min(sz(A), sz(B)); i++) { if (abs(xa - xb) > DIF) break; if (A[i] != B[i]) aft = 1; if (aft) { xa = (2 * xa) + (A[i] - '0'); xb = (2 * xb) + (B[i] - '0'); } int upa = sz(A) - i - 1, upb = sz(B) - i - 1; ans = min(ans, upa + upb + abs(xa - xb)); } cout << ans << nl; return 0; }
#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...