Submission #492851

#	Time	Username	Problem	Language	Result	Execution time	Memory
492851		Sunset	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	7472 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())

using namespace std;

const int N = 100500;

int ga[3][3][N];

void init(std::string a, std::string b) {
  vector<int> c2i(128);
  c2i['A'] = 0;
  c2i['T'] = 1;
  c2i['C'] = 2;
  for (int i = 0; i < sz(a); ++i) {
    for (int x = 0; x < 3; ++x)
      for (int y = 0; y < 3; ++y)
        ga[x][y][i + 1] = ga[x][y][i];
    ga[c2i[a[i]]][c2i[b[i]]][i + 1]++;
  }
}

int get_distance(int l, int r) {
  int a[3][3];
  ++r;
  for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j)
      a[i][j] = ga[i][j][r] - ga[i][j][l];
  int ans = 0;
  for (int i = 0; i < 3; ++i)
    for (int j = 0; j < i; ++j) {
      int x = min(a[i][j], a[j][i]);
      ans += x;
      a[i][j] -= x;
      a[j][i] -= x;
    }
  if (a[0][1] != a[1][2] || a[1][2] != a[2][0]) return -1;
  if (a[1][0] != a[2][1] || a[2][1] != a[0][2]) return -1;
  ans += a[0][1] * 2;
  ans += a[1][0] * 2;
	return ans;
}

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