Submission #1142784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142784		LucaLucaM	Crossing (JOI21_crossing)	C++20	26 / 100	7092 ms	2244 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <set>

std::set<std::string> st;

std::string join(std::string a, std::string b) {
  std::string ret;
  for (int i = 0; i < (int) a.size(); i++) {
    if (a[i] == b[i]) {
      ret += a[i];
    } else {
      ret += 'J' ^ 'O' ^ 'I' ^ a[i] ^ b[i];
    }
  }
  return ret;
}

void go(std::string s) {
  if (st.count(s)) {
    return;
  }
  st.insert(s);
  for (const auto &str : st) {
    go(join(s, str));
  }
}

void get(std::string s) {
  for (const auto &str : st) {
    bool ok = true;
    for (int i = 0; i < (int) s.size(); i++) {
      if (s[i] != str[i]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      std::cout << "Yes\n";
      return;
    }
  }
  std::cout << "No\n";
}

int main() {
  #ifdef LOCAL
freopen("input.txt", "r", stdin);
  #endif

  int n;
  std::cin >> n;

  std::string a, b, c;
  std::cin >> a >> b >> c;

  go(a);
  go(b);
  go(c);

  int q;
  std::cin >> q;

  std::string str;
  std::cin >> str;

  get(str);

  for (int i = 1; i <= q; i++) {
    int l, r;
    char c;
    std::cin >> l >> r >> c;
    l--, r--;
    for (int j = l; j <= r; j++) {
      str[j] = c;
    }
    get(str);
  }

  return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 0 / 23
• Subtask 3: 23 / 23
• Subtask 4: 0 / 51