제출 #1289322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289322		OmarAlimammadzade	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	24 ms	7320 KiB

dna

#include "dna.h"
#include "bits/stdc++.h"
using namespace std;

const int N = 1e5 + 5;
int AT[N], AC[N];
int CA[N], CT[N];
int TA[N], TC[N];
int pA[N], qA[N];
int pC[N], qC[N];
int pT[N], qT[N];
int n;

void init(string p, string q) {
  int n = p.size();
  p = " " + p;
  q = " " + q;
  for (int i = 1; i <= n; i++) {
    AT[i] = AT[i - 1] + (p[i] == 'A' and q[i] == 'T');
    AC[i] = AC[i - 1] + (p[i] == 'A' and q[i] == 'C');
    CA[i] = CA[i - 1] + (p[i] == 'C' and q[i] == 'A');
    CT[i] = CT[i - 1] + (p[i] == 'C' and q[i] == 'T');
    TA[i] = TA[i - 1] + (p[i] == 'T' and q[i] == 'A');
    TC[i] = TC[i - 1] + (p[i] == 'T' and q[i] == 'C');
    pA[i] = pA[i - 1] + (p[i] == 'A');
    pC[i] = pC[i - 1] + (p[i] == 'C');
    pT[i] = pT[i - 1] + (p[i] == 'T');
    qA[i] = qA[i - 1] + (q[i] == 'A');
    qC[i] = qC[i - 1] + (q[i] == 'C');
    qT[i] = qT[i - 1] + (q[i] == 'T');
  }
}

int get_distance(int x, int y) {
  x++, y++;
  if (pA[y] - pA[x - 1] != qA[y] - qA[x - 1] ||
      pC[y] - pC[x - 1] != qC[y] - qC[x - 1] ||
      pT[y] - pT[x - 1] != qT[y] - qT[x - 1]) {
    return -1;
  }
  int at = AT[y] - AT[x - 1], ac = AC[y] - AC[x - 1];
  int ca = CA[y] - CA[x - 1], ct = CT[y] - CT[x - 1];
  int ta = TA[y] - TA[x - 1], tc = TC[y] - TC[x - 1];
  int ans = 0;

  int atta = min(at, ta);
  ans += atta;
  at -= atta;
  ta -= atta;

  int acca = min(ac, ca);
  ans += acca;
  ac -= acca;
  ca -= acca;

  int cttc = min(ct, tc);
  ans += cttc;
  ct -= cttc;
  tc -= cttc;

  if (!(at == tc && tc == ca) || !(ac == ta && ta == ct)) {
    return -1;
  }

  ans += 2 * at;
  ans += 2 * ac;

  return ans;
}

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