Submission #439736

#	Time	Username	Problem	Language	Result	Execution time	Memory
439736		madlogic	Mutating DNA (IOI21_dna)	C++17	100 / 100	217 ms	34060 KiB

dna

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

int n;
string s, t;
vector<vector<int>> pref1, pref2, inds;
vector<string> pr;
map<string, vector<vector<int>>> mp;

void init(std::string a, std::string b) {
  s = a;
  t = b;
  n = (int) s.length();
  pref1 = vector<vector<int>>(n, vector<int>(26));
  pref2 = vector<vector<int>>(n, vector<int>(26));
  pref1[0][s[0] - 'A']++;
  pref2[0][t[0] - 'A']++;
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 26; j++) {
      pref1[i][j] = pref1[i - 1][j];
      pref2[i][j] = pref2[i - 1][j];
    }
    pref1[i][s[i] - 'A']++;
    pref2[i][t[i] - 'A']++;
  }
  auto getPrefix = [&](char c, char d) {
    vector<int> pref(n);
    if (s[0] == c && t[0] == d) {
      pref[0] = 1;
    }
    for (int i = 1; i < n; i++) {
      pref[i] = pref[i - 1];
      if (s[i] == c && t[i] == d) {
        pref[i]++;
      }
    }
    return pref;
  };
  string str = "ACT";
  int m = (int) str.length();
  for (int i = 0; i < m; i++) {
    for (int j = i + 1; j < m; j++) {
      string cur;
      cur += str[i];
      cur += str[j];
      vector<int> pref1 = getPrefix(str[i], str[j]);
      vector<int> pref2 = getPrefix(str[j], str[i]);
      mp[cur].push_back(pref1);
      mp[cur].push_back(pref2);
    }
  }
  inds.resize(26);
  for (int i = 0; i < n; i++) {
    if (s[i] == t[i]) {
      inds[s[i] - 'A'].push_back(i);
    }
  }
}

int get_distance(int x, int y) {
  for (int j = 0; j < 26; j++) {
    int cnt1 = pref1[y][j] - (x > 0 ? pref1[x - 1][j] : 0);
    int cnt2 = pref2[y][j] - (x > 0 ? pref2[x - 1][j] : 0);
    if (cnt1 != cnt2) {
      return -1;
    }
  }
  int cntA = pref1[y][0] - (x > 0 ? pref1[x - 1][0] : 0);
  int len = y - x + 1;
  for (int i = 0; i < 26; i++) {
    if (inds[i].empty()) {
      continue;
    }
    auto ub = upper_bound(inds[i].begin(), inds[i].end(), y);
    auto lb = lower_bound(inds[i].begin(), inds[i].end(), x);
    if (ub == inds[i].begin()) {
      continue;
    }
    if (lb == inds[i].end()) {
      continue;
    }
    --ub;
    int aa = ub - inds[i].begin();
    int bb = lb - inds[i].begin();
    swap(aa, bb);
    len -= (bb - aa + 1);
    if (i == 0) {
      cntA -= (bb - aa + 1);
    }
  }
  int res = 0;
  for (auto& [str, pref] : mp) {
    int cnt1 = pref[0][y] - (x > 0 ? pref[0][x - 1] : 0);
    int cnt2 = pref[1][y] - (x > 0 ? pref[1][x - 1] : 0);
    int rem = min(cnt1, cnt2);
    if (str[0] == 'A') {
      cntA -= rem;  
    }
    len -= 2 * rem;
    res += rem;
  } 
  res += cntA;
  len -= cntA;
	return res + len / 2;  
}

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