Submission #1176282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176282		Kanon	Hieroglyphs (IOI24_hieroglyphs)	C++20	100 / 100	205 ms	28256 KiB

hieroglyphs

#include <bits/stdc++.h>
#include "hieroglyphs.h"

using namespace std;


class segtree {
  public:
  struct node {
    int min_val = INT_MAX;
    void apply(int l, int r, int v) {
      min_val = v;
    }
  };

  node unite(const node &a, const node &b) const {
    node res;
    res.min_val = min(a.min_val, b.min_val);
    return res;
  }

  inline void push(int x, int l, int r) {
  }

  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }

  int n;
  vector<node> tree;

  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }

  template <typename M, typename... T>
  void build(int x, int l, int r, const vector<M> &v, const T&... t) {
    if (l == r) {
      tree[x].apply(l, r, v[l], t...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v, t...);
    build(z, y + 1, r, v, t...);
    pull(x, z);
  }

  template <typename M, typename... T>
  segtree(const vector<M> &v, const T&... t) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v, t...);
  }

  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }

  segtree(){};

  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }

  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }

  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }

  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }

  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }

};

vector<int> ucs (vector<int> a, vector<int> b) {
  int n = a.size();
  int m = b.size();
  int Total_number = max(*max_element(a.begin(), a.end()), *max_element(b.begin(), b.end())) + 1;
  vector<vector<int>> A_postions_of_num(Total_number, vector<int>(1, -1));
  vector<vector<int>> B_postions_of_num(Total_number, vector<int>(1, -1));
  for (int i = 0; i < n; i++) {
    A_postions_of_num[a[i]].push_back(i);
  }
  for (int i = 0; i < m; i++) {
    B_postions_of_num[b[i]].push_back(i);
  }
  for (int i = 0; i < Total_number; i++) {
    A_postions_of_num[i].push_back(n);
    B_postions_of_num[i].push_back(m);
  }

  auto Nearest_next_B = [&](int pos, int val, int dir) {
    if (pos == m && dir == +1) return m;
    if (pos == -1 && dir == -1) return -1;
    auto it = lower_bound(B_postions_of_num[val].begin(), B_postions_of_num[val].end(), pos);
    if (dir == +1) {
      assert(it != B_postions_of_num[val].end());
      if (*it == pos) {
        assert(next(it) != B_postions_of_num[val].end());
        it++;
        return *it;
      } else {
        return *it;
      }
    } else {
      assert(it != B_postions_of_num[val].begin());
      it--;
      return *it;
    }
  };
  auto Nearest_next_A = [&](int pos, int val, int dir) {
    if (pos == n && dir == +1) return n;
    if (pos == -1 && dir == -1) return -1;
    auto it = lower_bound(A_postions_of_num[val].begin(), A_postions_of_num[val].end(), pos);
    if (dir == +1) {
      assert(it != A_postions_of_num[val].end());
      if (*it == pos) {
        assert(next(it) != A_postions_of_num[val].end());
        it++;
        return *it;
      } else {
        return *it;
      }
    } else {
      assert(it != A_postions_of_num[val].begin());
      it--;
      return *it;
    }
  };

  vector<int> Left_most_reached_in_B_of_A(n, m);
  vector<int> Left_most_reached_in_A_of_B(m, n);

  for (int rot = 0; rot < 2; rot++) {
    segtree Left_B_reached_from_a(n);
    for (int pos_a = 0; pos_a < n; pos_a++) {
      int prev_a_same_val = Nearest_next_A(pos_a, a[pos_a], -1);
      int prev_b_reached = prev_a_same_val == -1 ? -1 : Left_B_reached_from_a.get(prev_a_same_val).min_val;
      if (prev_a_same_val < pos_a - 1) {
        prev_b_reached = min(prev_b_reached, Left_B_reached_from_a.get(prev_a_same_val + 1, pos_a - 1).min_val);
      }
      int cur_b_reached = Nearest_next_B(prev_b_reached, a[pos_a], +1);
      Left_B_reached_from_a.modify(pos_a, pos_a, cur_b_reached);
      Left_most_reached_in_B_of_A[pos_a] = cur_b_reached;
    }
    swap(n, m);
    swap(a, b);
    swap(Left_most_reached_in_B_of_A, Left_most_reached_in_A_of_B);
    swap(A_postions_of_num, B_postions_of_num);
  }

  vector<bool> A_must(n);
  vector<bool> B_must(m);
  bool matched = true;
  for (int num = 0; num < Total_number; num++) {
    int A_num_sz = A_postions_of_num[num].size();
    int B_num_sz = B_postions_of_num[num].size();
    if (A_num_sz >= B_num_sz) {
      int cnt = 0;
      int B_pos_last_matched = m;
      for (int a_pos_id = A_num_sz - 2; a_pos_id >= 1; a_pos_id--) {
        int a_pos = A_postions_of_num[num][a_pos_id];
        assert(a[a_pos] == num);
        int b_far_pos = Left_most_reached_in_B_of_A[a_pos];
        if (b_far_pos >= B_pos_last_matched) continue;
        int next_B_match = Nearest_next_B(B_pos_last_matched, num, -1);
        B_pos_last_matched = next_B_match;
        A_must[a_pos] = true;
        cnt++;
      }
      if (cnt != B_num_sz - 2) {
        matched = false;
        break;
      }
    }
    if (B_num_sz >= A_num_sz) {
      int cnt = 0;
      int A_pos_last_matched = n;
      for (int b_pos_id = B_num_sz - 2; b_pos_id >= 1; b_pos_id--) {
        int b_pos = B_postions_of_num[num][b_pos_id];
        assert(b[b_pos] == num);
        int a_far_pos = Left_most_reached_in_A_of_B[b_pos];
        if (a_far_pos >= A_pos_last_matched) continue;
        int next_A_match = Nearest_next_A(A_pos_last_matched, num, -1);
        A_pos_last_matched = next_A_match;
        B_must[b_pos] = true;
        cnt++;
      }
      if (cnt != A_num_sz - 2) {
        matched = false;
        break;
      }
    }
    if (A_num_sz < B_num_sz) for (int i : A_postions_of_num[num]) if (i > -1 && i < n) A_must[i] = true;
    if (B_num_sz < A_num_sz) for (int i : B_postions_of_num[num]) if (i > -1 && i < m) B_must[i] = true;
  }

  if (!matched) {
    return (vector<int>) {-1};
  }

  vector<int> A_ret_pos = {-1};
  vector<int> B_ret_pos = {-1};
  for (int i = 0; i < n; i++) if (A_must[i]) A_ret_pos.push_back(i);
  for (int i = 0; i < m; i++) if (B_must[i]) B_ret_pos.push_back(i);
  A_ret_pos.push_back(n);
  B_ret_pos.push_back(m);
  assert(A_ret_pos.size() == B_ret_pos.size());
  int sz = A_ret_pos.size();
  for (int i = 1; i < sz - 1; i++) if (a[A_ret_pos[i]] != b[B_ret_pos[i]]) return (vector<int>) {-1};
  vector<int> id_in_A_ret(n);
  vector<int> id_in_B_ret(m);
  for (int i = 0; i < n; i++) {
    id_in_A_ret[i] = A_must[i];
    if (i > 0) id_in_A_ret[i] += id_in_A_ret[i - 1];
  }
  for (int i = 0; i < m; i++) {
    id_in_B_ret[i] = B_must[i];
    if (i > 0) id_in_B_ret[i] += id_in_B_ret[i - 1];
  }
  for (int a_pos = 0; a_pos < n; a_pos++) {
    if (A_must[a_pos]) continue;
    int b_left_pos = Left_most_reached_in_B_of_A[a_pos];
    assert(b_left_pos > -1);
    if (b_left_pos >= m) continue;
    if (id_in_A_ret[a_pos] > id_in_B_ret[b_left_pos]) return (vector<int>) {-1};
  }

  for (int b_pos = 0; b_pos < m; b_pos++) {
    if (B_must[b_pos]) continue;
    int a_left_pos = Left_most_reached_in_A_of_B[b_pos];
    assert(a_left_pos > -1);
    if (a_left_pos >= n) continue;
    if (id_in_B_ret[b_pos] > id_in_A_ret[a_left_pos]) return (vector<int>) {-1};
  }

  vector<int> ret;
  for (int i : A_ret_pos) if (i > -1 && i < n) ret.push_back(a[i]);
  return ret;
}

• Subtask 0: 0 / 0
• Subtask 1: 3 / 3
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 16 / 16
• Subtask 5: 14 / 14
• Subtask 6: 42 / 42