Submission #1009658

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009658		somefjord	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	6492 KiB

dna

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

using namespace std;

string as, bs;
vector<int> cc[9];

char letters[3] = {'A', 'T', 'C'};

void init(string a, string b) {
  as = a;
  bs = b;

  int n = a.length();
  for (int i = 0; i < 9; ++i) {
    cc[i].resize(n + 2, 0);
  }

  for (int i = 1; i <= n; ++i) {
    for (int cx = 0; cx < 3; ++cx) {
      for (int cy = 0; cy < 3; ++cy) {
        cc[cy * 3 + cx][i] =
            cc[cy * 3 + cx][i - 1] +
            (as[i - 1] == letters[cx] && bs[i - 1] == letters[cy]);
        // printf("cc[%d][%d] = %c %c\n", cx, cy, letters[cx], letters[cy]);
      }
    }
  }
}

int get_distance(int x, int y) {
  y++;

  /*
    cc[0][0] = A A 0
    cc[1][1] = T T 4
    cc[2][2] = C C 8

    cc[0][1] = A T 1
    cc[1][0] = T A 3

    cc[0][2] = A C 2
    cc[2][0] = C A 6

    cc[1][2] = T C 5
    cc[2][1] = C T 7
   */
  int ccs[9];
  for (int i = 0; i < 9; ++i)
    ccs[i] = cc[i][y] - cc[i][x];

  if (ccs[1] + ccs[2] != ccs[3] + ccs[6] ||
      ccs[3] + ccs[5] != ccs[1] + ccs[7] || ccs[6] + ccs[7] != ccs[2] + ccs[5])
    return -1;

  int count = 0;
  int remaining = ccs[1] + ccs[2] + ccs[3] + ccs[5] + ccs[6] + ccs[7];

  int r1 = min(ccs[1], ccs[3]);
  remaining -= r1 * 2;
  count += r1;

  int r2 = min(ccs[2], ccs[6]);
  remaining -= r2 * 2;
  count += r2;

  int r3 = min(ccs[5], ccs[7]);
  remaining -= r3 * 2;
  count += r3;

  if (remaining)
    count += (remaining / 3) * 2;

  return count;
}

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