Submission #1077198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077198		juicy	Mutating DNA (IOI21_dna)	C++17	100 / 100	48 ms	8728 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

namespace {
  const int N = 1e5 + 5;

  int n;
  int A[3][N], B[3][N], pf[6][N];
  std::vector<char> c = {'A', 'T', 'C'};
  std::vector<std::array<char, 2>> pat = {{'A', 'T'}, {'T', 'A'}, {'A', 'C'}, {'C', 'A'}, {'T', 'C'}, {'C', 'T'}}; 
  int qry(int l, int r, int *pf) {
    return pf[r] - (l ? pf[l - 1] : 0);
  }
}

void init(std::string a, std::string b) {
  n = a.size();
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      A[j][i] = i ? A[j][i - 1] : 0;
      B[j][i] = i ? B[j][i - 1] : 0;
    } 
    for (int j = 0; j < 6; ++j) {
      pf[j][i] = i ? pf[j][i - 1] : 0;
    }
    ++A[find(c.begin(), c.end(), a[i]) - c.begin()][i];
    ++B[find(c.begin(), c.end(), b[i]) - c.begin()][i];
    if (a[i] != b[i]) {
      ++pf[find(pat.begin(), pat.end(), std::array<char, 2>{a[i], b[i]}) - pat.begin()][i];
    }
  }
}

int get_distance(int x, int y) {
  for (int j = 0; j < 3; ++j) {
    if (qry(x, y, A[j]) != qry(x, y, B[j])) {
      return -1;
    }
  }
  std::array<int, 6> cnt{};
  for (int i = 0; i < 6; ++i) {
    cnt[i] = qry(x, y, pf[i]);
  }
  int res = 0, tot = 0;
  for (int i = 0; i < 6; i += 2) {
    int k = std::min(cnt[i], cnt[i + 1]);
    cnt[i] -= k;
    cnt[i + 1] -= k;
    res += k;
    tot += cnt[i] + cnt[i + 1];
  }
  return res + 2 * tot / 3;
}

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