Submission #1176990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176990		LmaoLmao	Board (CEOI13_board)	C++20	100 / 100	48 ms	4688 KiB

board

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, l, r) for(int i = (l); i < (r); ++i)
#define ROF(i, r, l) for(int i = (r)-1; i >= (l); --i)

#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second

#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define pb push_back
#define eb emplace_back
#define sz(v) (int)v.size()
#define compact(v) v.erase(unique(all(v)), end(v))

#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
      bool minimize(T& a, const T& b){
            if(a > b) return a = b, true;
            return false;
      }

template<typename T>
      bool maximize(T& a, const T& b){
            if(a < b) return a = b, true;
            return false;
      }

using ll = long long;
using db = double;
using ld = long double;
using ull = unsigned long long;

using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using vc = vector<char>;
using vb = vector<bool>;

using vpi = vector<pi>;
using vpl = vector<pl>;

using vvi = vector<vi>;
using vvl = vector<vl>;
using vvc = vector<vc>;

void setIO(){
      ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
      freopen("task.inp", "r", stdin);
      freopen("task.out", "w", stdout);
//#else
//      freopen("LYRA.inp", "r", stdin);
//      freopen("LYRA.out", "w", stdout);
#endif // LOCAL
}

const int MAX = 1e5 + 5;

int res;

struct SegmentTree{
      vi ones, lazy;
      SegmentTree(int n) : ones(n * 5, 0), lazy(n * 5, -1) {}

      void apply(int id, int l, int r, int val){
            ones[id] = (r - l + 1) * val;
            lazy[id] = val;
      }

      void down(int id, int l, int r, int mid){
            if(lazy[id] != -1){
                  apply(id << 1, l, mid, lazy[id]);
                  apply(id << 1 | 1, mid + 1, r, lazy[id]);
                  lazy[id] = -1;
            }
      }

      void update(int id, int l, int r, int u, int v, int val){
            if(u <= l && r <= v) apply(id, l, r, val);
            else{
                  int mid = l + r >> 1;
                  down(id, l, r, mid);
                  if(u <= mid) update(id << 1, l, mid, u, v, val);
                  if(mid < v)  update(id << 1 | 1, mid + 1, r, u, v, val);
                  ones[id] = ones[id << 1] + ones[id << 1 | 1];
            }
      }

      int f0(int id, int l, int r, int u, int v){
//            cout << dbg(id) << dbg(l) << dbg(r) << dbg(u) << dbg(v) << dbg(ones[id]) << '\n';
            if(u <= l && r <= v){
                  if(ones[id] != r - l + 1) {
//                        cout << "ok\n";
                        while(l < r){
//                              cout << dbg(l) << dbg(r) << '\n';
                              int mid = l + r >> 1;
                              down(id, l, r, mid);
                              if(ones[id << 1 | 1] != r - mid) id = id << 1 | 1, l = mid + 1;
                              else id = id << 1, r = mid;
                        }
//                        cout << dbg(l) << '\n';
                        return l;
                  }
                  return -1;
            } else{
                  int mid = l + r >> 1;
                  down(id, l, r, mid);
                  if(mid < v){
                        int tmp = f0(id << 1 | 1, mid + 1, r, u, v);
                        if(tmp != -1) return tmp;
                  }
                  return f0(id << 1, l, mid, u, v);
            }
      }

      void debug(int id, int l, int r, int u, int v){
            if(l == r) {
                  cout << ones[id];
                  if(l == v) cout << '\n';
            }
            else{
                  int mid = l + r >> 1;
                  down(id, l, r, mid);
                  if(u <= mid) debug(id << 1, l, mid, u, v);
                  if(mid < v)  debug(id << 1 | 1, mid + 1, r, u, v);
            }
      }

      int f1(int id, int l, int r, int u, int v){
            if(u <= l && r <= v){
                  if(ones[id] > 0) {
                        while(l < r){
                              int mid = l + r >> 1;
                              down(id, l, r, mid);
                              if(ones[id << 1 | 1] > 0) id = id << 1 | 1, l = mid + 1;
                              else id = id << 1, r = mid;
                        }
                        return l;
                  }
                  return -1;
            } else{
                  int mid = l + r >> 1;
                  down(id, l, r, mid);
                  if(mid < v){
                        int tmp = f1(id << 1 | 1, mid + 1, r, u, v);
                        if(tmp != -1) return tmp;
                  }
                  return f1(id << 1, l, mid, u, v);
            }
      }

      int get_bit(int id, int l, int r, int pos){
            if(l == r) return (ones[id] ? 1 : 0);
            else{
                  int mid = l + r >> 1;
                  down(id, l, r, mid);
                  if(pos <= mid) return get_bit(id << 1, l, mid, pos);
                  else return get_bit(id << 1 | 1, mid + 1, r, pos);
            }
      }
};

string construct_into_bits(const string& S){
      int cur = 0;
      int N = sz(S);
      SegmentTree tr(N);

      for(auto c : S){
            if(c == '1'){
                  ++cur;
                  tr.update(1, 1, N, cur, cur, 0);
//                  cout << "Add : " << 0 << '\n';
            }

            if(c == '2'){
                  ++cur;
                  tr.update(1, 1, N, cur, cur, 1);
//                  cout << "Add : " << 1 << '\n';
            }

            if(c == 'U'){
                  --cur;
//                  cout << "deleted\n";
            }

            if(c == 'L'){
                  //first find 1 from the end of [1...cur]
                  int pos = tr.f1(1, 1, N, 1, cur);
                  assert(pos != -1);
                  tr.update(1, 1, N, pos, pos, 0);
                  if(pos < cur) tr.update(1, 1, N, pos+1, cur, 1);
//                  cout << "invert L : " << pos << '\n';
            }

            if(c == 'R'){
                  //the opposite
                  int pos = tr.f0(1, 1, N, 1, cur);
                  assert(pos != -1 && true);
//                  cout << dbg(pos) << '\n';
                  tr.update(1, 1, N, pos, pos, 1);
                  if(pos < cur) tr.update(1, 1, N, pos+1, cur, 0);
//                  cout << "invert R : " << pos << '\n';
            }

//            cout << '\n';

//            tr.debug(1, 1, N, 1, cur);
      }

      string bits = "";
      FOR(i, 1, cur+1){
            bits += char('0' + tr.get_bit(1, 1, N, i));
      }
      return bits;
}

int main(){
      setIO();

      string A, B;
      cin >> A >> B;

      A = construct_into_bits(A);
      B = construct_into_bits(B);
//
//      cout << A << '\n';
//      cout << B << '\n';
//      return 0;

      int base = 0;
      while(sz(A) != sz(B)){
            if(sz(A) > sz(B)){
                  A.pop_back();
            } else{
                  B.pop_back();
            }
            ++base;
      }

      if(A > B){ //decide who is on the left
            swap(A, B);
      }

      int N = sz(A);
      int result = 2 * N;
      int d = 0;
//      cout << result << ' ' << N << '\n';
      FOR(i, 0, N){
            if(A[i] < B[i]) d = d * 2 + 1;
            if(A[i] > B[i]) d = d * 2 - 1;
            if(A[i] == B[i]) d = d * 2;

            if(d > 2 * N) break;
            minimize(result, d + (N - i - 1) * 2);
      }

      cout << result + base << '\n';

      return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10