Submission #437161

#	Time	Username	Problem	Language	Result	Execution time	Memory
437161		flashmt	Mutating DNA (IOI21_dna)	C++17	100 / 100	69 ms	8452 KiB

dna

#include <bits/stdc++.h>
using namespace std;

int n, cntA[3][100100], cntB[3][100100], cntAB[3][3][100100];

void init(string a, string b)
{
  int m[256];
  m['A'] = 0;
  m['C'] = 1;
  m['T'] = 2;
  n = a.size();
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < 3; j++)
    {
      cntA[j][i + 1] = cntA[j][i];
      cntB[j][i + 1] = cntB[j][i];
      for (int k = 0; k < 3; k++)
        cntAB[j][k][i + 1] = cntAB[j][k][i];
    }
    cntA[m[a[i]]][i + 1]++;
    cntB[m[b[i]]][i + 1]++;
    cntAB[m[a[i]]][m[b[i]]][i + 1]++;
  }
}

int get_distance(int x, int y) {
  y++;
  for (int i = 0; i < 3; i++)
    if (cntA[i][y] - cntA[i][x] != cntB[i][y] - cntB[i][x])
      return -1;

  int ans = 0, share = 0;
  for (int i = 0; i < 3; i++)
    for (int j = i + 1; j < 3; j++)
    {
      int u = cntAB[i][j][y] - cntAB[i][j][x];
      int v = cntAB[j][i][y] - cntAB[j][i][x];
      ans += min(u, v);
      share += abs(u - v);
    }
  assert(share % 3 == 0);
  ans += share / 3 * 2;
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:22:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |     cntA[m[a[i]]][i + 1]++;
      |                ^
dna.cpp:23:16: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |     cntB[m[b[i]]][i + 1]++;
      |                ^
dna.cpp:24:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |     cntAB[m[a[i]]][m[b[i]]][i + 1]++;
      |                 ^
dna.cpp:24:26: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |     cntAB[m[a[i]]][m[b[i]]][i + 1]++;
      |                          ^

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