Submission #441067

#	Time	Username	Problem	Language	Result	Execution time	Memory
441067		lalafa	Mutating DNA (IOI21_dna)	C++17	71 / 100	1579 ms	2396 KiB

dna

#include <string>
#include <algorithm>

static std::string a_, b_;
void init(std::string a, std::string b) {
  a_ = a;
  b_ = b;
}
int get_distance(int x, int y) {
  int c[3] = {0,0,0};
  int cc[3][3];
  for (int i = 0; i <9 ; ++i) cc[i/3][i%3] = 0;
  auto v = [](char c) { return c == 'A' ? 0 : c == 'C' ? 1 : 2; };
  for (int i = x; i <= y; ++i) {
    int v0 = v(a_[i]), v1 = v(b_[i]);
    ++cc[v0][v1];
    ++c[v0];
    --c[v1];
  }
  if (c[0] != 0 || c[1] != 0 || c[2] != 0) return -1;
  int res = 0, mv = 0;
  for (int v0 = 0; v0 < 2; ++v0) {
    for (int v1 = v0 + 1; v1 < 3; ++v1) {
      int vlo = std::min(cc[v0][v1], cc[v1][v0]);
      int vhi = std::max(cc[v0][v1], cc[v1][v0]);
      res += vlo;
      mv = std::max(mv, vhi - vlo);
    }
  }
  return res + 2 * mv;
}

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 0 / 13
• Subtask 4: 28 / 28
• Subtask 5: 0 / 16