Submission #1009633

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009633		somefjord	Mutating DNA (IOI21_dna)	C++17	56 / 100	26 ms	6484 KiB

dna

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

using namespace std;

string as, bs;
vector<int> cc[3];
vector<int> lc[6];

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

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

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

  for (int i = 1; i <= n; ++i) {
    for (int ci = 0; ci < 3; ++ci) {
      cc[ci][i] = cc[ci][i - 1] +
                  ((as[i - 1] == combos[ci][0] && bs[i - 1] == combos[ci][1]) ||
                   (as[i - 1] == combos[ci][1] && bs[i - 1] == combos[ci][0]));
      lc[ci][i] = lc[ci][i - 1] + (as[i - 1] == letters[ci]);
      lc[ci + 3][i] = lc[ci + 3][i - 1] + (bs[i - 1] == letters[ci]);
    }
  }
}

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

  int c1 = cc[0][y] - cc[0][x];
  int c2 = cc[1][y] - cc[1][x];
  int c3 = cc[2][y] - cc[2][x];
  int lc1 = lc[0][y] - lc[0][x];
  int lc2 = lc[1][y] - lc[1][x];
  int lc3 = lc[2][y] - lc[2][x];
  int lc4 = lc[3][y] - lc[3][x];
  int lc5 = lc[4][y] - lc[4][x];
  int lc6 = lc[5][y] - lc[5][x];

  int count = 0;
  if (lc1 != lc4 || lc2 != lc5 || lc3 != lc6)
    return -1;
  int remaining = c1 + c2 + c3;

  if (!(c1 & 1)) {
    remaining -= c1;
    count += c1 / 2;
  }
  if (!(c2 & 1)) {
    remaining -= c2;
    count += c2 / 2;
  }
  if (!(c3 & 1)) {
    remaining -= c3;
    count += c3 / 2;
  }

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

  return count;
}

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