Submission #468390

#	Time	Username	Problem	Language	Result	Execution time	Memory
468390		fun_day	Mutating DNA (IOI21_dna)	C++17	100 / 100	65 ms	10444 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