Submission #757764

#	Time	Username	Problem	Language	Result	Execution time	Memory
757764		taher	Mutating DNA (IOI21_dna)	C++17	100 / 100	56 ms	11768 KiB

dna

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> a, b, c, a_t, b_t, c_t;
vector<vector<int>> pref;
vector<char> q = {'A', 'T', 'C'};

void init(string s, string t) {
  n = (int)s.length();
  a.resize(n + 1); b.resize(n + 1); c.resize(n + 1); a_t.resize(n + 1); b_t.resize(n + 1); c_t.resize(n + 1); pref.resize(n + 1, vector<int>(6));
  for (int i = 0 ; i < n ; i++) {
    int cnt = 0;
    for (int j = 0 ; j < (int)q.size() ; j++) {
      for (int m = 0 ; m < (int)q.size() ; m++) {
        char one = q[j], two = q[m];
        if (one == two) continue;
        pref[i + 1][cnt] = pref[i][cnt] + (s[i] == one && t[i] == two);
        cnt++;
      }
    }
  }
  for (int i = 0 ; i < n ; i++) {
    a[i + 1] = a[i] + (s[i] == 'A');
    a_t[i + 1] = a_t[i] + (t[i] == 'A');
    b[i + 1] = b[i] + (s[i] == 'T');
    b_t[i + 1] = b_t[i] + (t[i] == 'T');
    c[i + 1] = c[i] + (s[i] == 'C');
    c_t[i + 1] = c_t[i] + (t[i] == 'C');
  }
  return ;
}

int get_distance(int x, int y) {
  if (a[y + 1] - a[x] == a_t[y + 1] - a_t[x] && b[y + 1] - b[x] == b_t[y + 1] - b_t[x] && c[y + 1] - c[x] == c_t[y + 1] - c_t[x]) {
    int AT = pref[y+1][0]-pref[x][0], AC = pref[y+1][1]-pref[x][1], TA = pref[y+1][2]-pref[x][2], TC = pref[y+1][3] -pref[x][3], CA = pref[y+1][4] - pref[x][4], CT = pref[y+1][5] - pref[x][5];
    int best = min(AT, TA) + min(AC, CA) + (max(AT, TA) - min(AT, TA)) * 2 + min(CT, TC);
    return best;
  }
  else return -1;
}

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