Submission #441079

#	Time	Username	Problem	Language	Result	Execution time	Memory
441079		lalafa	Mutating DNA (IOI21_dna)	C++17	0 / 100	44 ms	5644 KiB

dna

#include <string>
#include <algorithm>

std::vector<int>ccc;
void init(std::string a, std::string b) {
  auto v = [](char c) { return c == 'A' ? 0 : c == 'C' ? 1 : 2; };

  int l = a.size();
  ccc.resize(l * 9 + 10, 0);
  for (int i = 0; i < l; ++i) {
    for(int j = 0; j < 9; ++j) ccc[i*9 + j + 9] = ccc[i*9 + j];
    int v9 =  v(a[i]) * 3 + v(b[i]);
    ccc[i*9 +v9 + 9] = ccc[i*9 + v9];
  }
}

int get_distance(int x, int y) {
  int c[3] = {0,0,0};
  int cc[3][3];
  for (int i = 0; i <9 ; ++i) {
    int v = ccc[y*9 + 9 + i] - ccc[x*9 + i];
    cc[i/3][i%3] = v;
    c[i/3] += v;
    c[i%3] -= v;
  }
  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: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16