Submission #1248517

#TimeUsernameProblemLanguageResultExecution timeMemory
1248517kaiboy게임판 (CEOI13_board)C++20
40 / 100
40 ms3144 KiB
#include <algorithm> #include <iostream> #include <cstring> using namespace std; const int N = 100000; const int M = 100000; const int N_ = 1 << 17; const int INF = 0x3f3f3f3f; char aa[N + 1], bb[M + 1]; int st0[N_ << 1], st1[N_ << 1], lz[N_], h_, n_; void put(int i) { swap(st0[i], st1[i]); if (i < n_) lz[i] ^= 1; } void pus(int i) { if (lz[i]) { int l = i << 1, r = l ^ 1; put(l), put(r), lz[i] = 0; } } void pul(int i) { if (!lz[i]) { int l = i << 1, r = l ^ 1; st0[i] = st0[r] != -1 ? st0[r] : st0[l]; st1[i] = st1[r] != -1 ? st1[r] : st1[l]; } } void push(int i) { for (int h = h_; h; h--) pus(i >> h); } void pull(int i) { while (i >>= 1) pul(i); } void build(int n) { h_ = 0, n_ = 1; while (n_ <= n) h_++, n_ <<= 1; for (int i = 0; i < n_; i++) st0[i + n_] = i, st1[i + n_] = -1, lz[i] = 0; for (int i = n_ - 1; i; i--) pul(i); } void update(int l, int r) { int l_ = l += n_, r_ = r += n_; push(l_), push(r_); for ( ; l <= r; l >>= 1, r >>= 1) { if (l & 1) put(l++); if (!(r & 1)) put(r--); } pull(l_), pull(r_); } int search0(int r) { int l = n_; push(r += n_); for ( ; l <= r; l >>= 1, r >>= 1) if (!(r & 1)) { if (st0[r] != -1) return st0[r]; r--; } return -1; } int search1(int r) { int l = n_; push(r += n_); for ( ; l <= r; l >>= 1, r >>= 1) if (!(r & 1)) { if (st1[r] != -1) return st1[r]; r--; } return -1; } int query(int i) { push(i += n_); return st0[i] == -1; } int transform(char *aa, int n) { int m = 0; build(n); for (int i = 0; i < n; i++) { char a = aa[i]; if (a == '1') m++; else if (a == '2') update(m, m), m++; else if (a == 'U') { if (query(m - 1)) update(m - 1, m - 1); m--; } else if (a == 'L') update(search1(m - 1), m - 1); else update(search0(m - 1), m - 1); } for (int h = 0; h < m; h++) aa[h] = query(h); return m; } int main() { cin >> aa >> bb; int n = strlen(aa), m = strlen(bb); n = transform(aa, n); m = transform(bb, m); if (n > m) swap(n, m), swap(aa, bb); int ans = INF, i_ = 0; while (i_ < n && aa[i_] == bb[i_]) i_++; for (int d = 0, i = i_; i <= n && i < i_ + 19; i++) { ans = min(ans, n - i + abs(d) + m - i); if (i < n) d = d * 2 + aa[i] - bb[i]; } cout << ans << '\n'; 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...