Submission #1118078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118078		repmann	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	9900 KiB

dna

#include <bits/stdc++.h>
using namespace std;
int N;
int I[256];
int PS[3][3][100006];
int A[3][100006];
int B[3][100006];
void init(string a, string b)
{
  I['A'] = 0;
  I['T'] = 1;
  I['C'] = 2;
  N = a.size();
  for(int i = 1; i <= N; i++)
  {
    for(int j = 0; j < 3; j++)
    {
      A[j][i] = A[j][i - 1];
      B[j][i] = B[j][i - 1];
      for(int k = 0; k < 3; k++) PS[j][k][i] = PS[j][k][i - 1];
    }
    PS[I[a[i - 1]]][I[b[i - 1]]][i]++;
    A[I[a[i - 1]]][i]++;
    B[I[b[i - 1]]][i]++;
  }
  return;
}
int get_distance(int L, int R)
{
  int RET = 0;
  L++; R++;
  if((A[0][R] - A[0][L - 1]) != (B[0][R] - B[0][L - 1])) return -1;
  if((A[1][R] - A[1][L - 1]) != (B[1][R] - B[1][L - 1])) return -1;
  if((A[2][R] - A[2][L - 1]) != (B[2][R] - B[2][L - 1])) return -1;
  int AT = PS[0][1][R] - PS[0][1][L - 1];
  int AC = PS[0][2][R] - PS[0][2][L - 1];
  int TA = PS[1][0][R] - PS[1][0][L - 1];
  int TC = PS[1][2][R] - PS[1][2][L - 1];
  int CA = PS[2][0][R] - PS[2][0][L - 1];
  int CT = PS[2][1][R] - PS[2][1][L - 1];
  int atswap = min(AT, TA);
  int acswap = min(AC, CA);
  int tcswap = min(TC, CT);
  RET += atswap + acswap + tcswap;
  AT -= atswap;
  AC -= acswap;
  TA -= atswap;
  TC -= tcswap;
  CA -= acswap;
  CT -= tcswap;
  RET += min({max(AT, TA), max(AC, CA), max(TC, CT)}) << 1;
  return RET;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:22:18: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |     PS[I[a[i - 1]]][I[b[i - 1]]][i]++;
      |                  ^
dna.cpp:22:31: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |     PS[I[a[i - 1]]][I[b[i - 1]]][i]++;
      |                               ^
dna.cpp:23:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |     A[I[a[i - 1]]][i]++;
      |                 ^
dna.cpp:24:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |     B[I[b[i - 1]]][i]++;
      |                 ^

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