Submission #1154300

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154300		equation_tracker	Mutating DNA (IOI21_dna)	C++20	56 / 100	500 ms	14628 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<vector<ll>> prefix_a {}, prefix_b {};
vector<ll> pref_d {};
string s, t;
void init(std::string a, std::string b) {
  s = a;
  t = b;
  prefix_a.resize(a.size() + 1, {0, 0, 0});
  pref_d.resize(a.size() + 1, 0);
  prefix_b.resize(b.size() + 1, {0, 0, 0});
  for (ll i = 1; i <= a.size(); i++) {
    pref_d[i] = (a[i-1] != b[i-1]);
    switch (a[i-1])
    {
    case 'A':
      prefix_a[i][0]++;
      break;
    case 'C':
      prefix_a[i][1]++;
      break;
    default:
      prefix_a[i][2]++;
      break;
    }
    switch (b[i - 1])
    {
    case 'A':
      prefix_b[i][0]++;
      break;
    case 'C':
      prefix_b[i][1]++;
      break;
    default:
      prefix_b[i][2]++;
      break;
    }
  }
  for (ll i = 1; i <= a.size(); i++) {
    pref_d[i] += pref_d[i-1];
    prefix_a[i][0] += prefix_a[i-1][0];
    prefix_a[i][1] += prefix_a[i-1][1];
    prefix_a[i][2] += prefix_a[i-1][2];
    prefix_b[i][0] += prefix_b[i-1][0];
    prefix_b[i][1] += prefix_b[i-1][1];
    prefix_b[i][2] += prefix_b[i-1][2];
  }
}

int get_distance(int x, int y) {
  string a = s, b = t;
  if (
    (prefix_a[y+1][0] - prefix_a[x][0] != prefix_b[y+1][0] - prefix_b[x][0]) ||
    (prefix_a[y+1][1] - prefix_a[x][1] != prefix_b[y+1][1] - prefix_b[x][1]) ||
    (prefix_a[y+1][2] - prefix_a[x][2] != prefix_b[y+1][2] - prefix_b[x][2])
  ) return -1;
  if (y - x <= 2) {
    if (x == y) return 0;
    else if (y == x + 1){
      return (s.substr(x, 2)!=t.substr(x, 2));
    } else {
      if (s.substr(x, 3) == t.substr(x, 3)) return 0;
      else if (a[x] == b[x] || a[x + 1] == b[x+1] || a[y] == b[y]) return 1;
      else return 2;
    }
  } else if (!prefix_a[a.size()][1] && !prefix_b[a.size()][1]) {

    return (pref_d[y+1] - pref_d[x]) / 2;
  }
  return 0;
}

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