Submission #615578

#	Time	Username	Problem	Language	Result	Execution time	Memory
615578		Minindu2006	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	8584 KiB

dna

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

int Aa[MX], Ab[MX], Ca[MX], Cb[MX], Ta[MX], Tb[MX], AC[MX], CA[MX], AT[MX], TA[MX], TC[MX], CT[MX];
void init(std::string a, std::string b)
{
  int n = a.size();
  for (int i = 0; i < n; i++)
  {
    Aa[i + 1] += Aa[i];
    Ca[i + 1] += Ca[i];
    Ta[i + 1] += Ta[i];
    Ab[i + 1] += Ab[i];
    Cb[i + 1] += Cb[i];
    Tb[i + 1] += Tb[i];
    AC[i + 1] += AC[i];
    AT[i + 1] += AT[i];
    CA[i + 1] += CA[i];
    TA[i + 1] += TA[i];
    CT[i + 1] += CT[i];
    TC[i + 1] += TC[i];
    char x = a[i], y = b[i];
    if (x == 'A')
      Aa[i + 1]++;
    if (x == 'C')
      Ca[i + 1]++;
    if (x == 'T')
      Ta[i + 1]++;

    if (y == 'A')
      Ab[i + 1]++;
    if (y == 'C')
      Cb[i + 1]++;
    if (y == 'T')
      Tb[i + 1]++;

    if (x == 'A' && y == 'C')
      AC[i + 1]++;
    if (x == 'A' && y == 'T')
      AT[i + 1]++;
    if (x == 'C' && y == 'A')
      CA[i + 1]++;
    if (x == 'C' && y == 'T')
      CT[i + 1]++;
    if (x == 'T' && y == 'A')
      TA[i + 1]++;
    if (x == 'T' && y == 'C')
      TC[i + 1]++;
  }
}


int get_distance(int x, int y)
{
  x++, y++;
  if(Aa[y] - Aa[x - 1] != Ab[y] - Ab[x - 1])
    return -1;
  if(Ca[y] - Ca[x - 1] != Cb[y] - Cb[x - 1])
    return -1;
  if(Ta[y] - Ta[x - 1] != Tb[y] - Tb[x - 1])
    return -1;
  int a = AC[y] - AC[x - 1];
  int b = CA[y] - CA[x - 1];
  int c = AT[y] - AT[x - 1];
  int d = TA[y] - TA[x - 1];
  int e = CT[y] - CT[x - 1];
  int f = TC[y] - TC[x - 1];

  if(a > b)
    swap(a, b);
  if(c > d)
    swap(c, d);
  if(e > f)
    swap(e, f);
  
  return a + c + e + (((b - a) + (d - c) + (f - e)) / 3) * 2;
}

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