Submission #1203374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203374		jejis	Mutating DNA (IOI21_dna)	C++20	100 / 100	23 ms	7332 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
const int N = 1e5 + 10;

int dp[N][3][3];
int diff[N][3];


// A, T, C
// 1, 2, 3

int dna_to_int(char a) {
  if (a == 'A') return 0;
  else if (a == 'T') return 1;
  else if (a == 'C') return 2;
}

int n;

void init(string a, string b) {
  a = '#' + a;
  b = '#' + b;

  n = a.size();

  for (int i = 1; i <= a.length(); i++) {
    int f = dna_to_int(a[i]),
        s = dna_to_int(b[i]);

    for (int x=0; x<3; x++) for (int y=0; y<3; y++) dp[i][x][y] = dp[i-1][x][y];
    for (int x=0; x<3; x++) diff[i][x] = diff[i-1][x];

    dp[i][f][s]++;
    diff[i][f]++;
    diff[i][s]--;
  }

}

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

  if (diff[y][0] - diff[x-1][0] != 0) return -1;
  if (diff[y][1] - diff[x-1][1] != 0) return -1;
  if (diff[y][2] - diff[x-1][2] != 0) return -1;

  int res = 0;
  int trans[3][3] = {{0}};

  for (int i = 0; i < 3; i++)
    for (int j = 0; j < 3; j++)
      trans[i][j] = dp[y][i][j] - dp[x-1][i][j];

  int t;

  // A - T && T - A
  t = min(trans[0][1], trans[1][0]);
  trans[0][1] -= t;
  trans[1][0] -= t;
  res += t;

  // A - C && C - A
  t = min(trans[0][2], trans[2][0]);
  trans[2][0] -= t;
  trans[0][2] -= t;
  res += t;

  // C - T && T - C
  t = min(trans[1][2], trans[2][1]);
  trans[2][1] -= t;
  trans[1][2] -= t;
  res += t;

  res += 2 * (trans[1][2] + trans[2][1]);
  return res;
}

Compilation message (stderr)

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

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