Submission #1132465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132465		lopkus	Mutating DNA (IOI21_dna)	C++20	100 / 100	70 ms	33096 KiB

dna

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

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int value(char c) {
  if (c == 'A') {
    return 0;
  }
  if (c == 'C') {
    return 1;
  }
  if (c == 'T') {
    return 2;
  }
}

vector<vector<int>> pa, pb;
vector<vector<vector<int>>> diff;

void init(string a, string b) {
  a = '$' + a; b = '$' + b;
  pa.resize(a.length() + 1);
  pb.resize(b.length() + 1);
  for (int i = 0; i <= a.length(); i++) {
    pa[i].resize(3);
  }
  for (int i = 0; i <= b.length(); i++) {
    pb[i].resize(3);
  }
  for (int i = 1; i <= a.length(); i++) {
    for (int j = 0; j < 3; j++) {
      pa[i][j] = pa[i - 1][j];
    }
    pa[i][value(a[i])]++;
  }
  for (int i = 1; i <= b.length(); i++) {
    for (int j = 0; j < 3; j++) {
      pb[i][j] = pb[i - 1][j];
    }
    pb[i][value(b[i])]++;
  }
  diff.resize(a.length() + 1);
  for (int i = 0; i <= a.length(); i++) {
    diff[i].resize(3);
    for (int j = 0; j < 3; j++) {
      diff[i][j].resize(3);
    }
  }
  for (int i = 1; i <= a.length(); i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        diff[i][j][k] = diff[i - 1][j][k];
      }
    }
    diff[i][value(a[i])][value(b[i])]++;
  }
}

int get_distance(int x, int y) {
  x++; y++;
  for (int i = 0; i < 3; i++) {
    if (pa[y][i] - pa[x - 1][i] != pb[y][i] - pb[x - 1][i]) {
      return -1;
    }
  }
  int ans = 0, sum = 0;
  for (int i = 0; i < 3; i++) {
    for (int j = i + 1; j < 3; j++) {
      ans += min(diff[y][i][j] - diff[x - 1][i][j], diff[y][j][i] - diff[x - 1][j][i]);
      sum += abs((diff[y][i][j] - diff[x - 1][i][j]) - (diff[y][j][i] - diff[x - 1][j][i]));
    }
  }
  ans += 2 * sum / 3;
  return ans;
} 

Compilation message (stderr)

dna.cpp: In function 'int value(char)':
dna.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
   22 | }
      | ^

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