Submission #468372

#	Time	Username	Problem	Language	Result	Execution time	Memory
468372		fun_day	Mutating DNA (IOI21_dna)	C++17	56 / 100	50 ms	8056 KiB

dna

#include <bits/stdc++.h>

using namespace std;

int n;
vector<long long> a , b , c , a_t , b_t , c_t , pref;

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);
  for(int i = 0 ; i < n ; i++){
    pref[i+1] = pref[i] + (s[i] != t[i]);    
  }
  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]){
    long long p = pref[y + 1] - pref[x];
    return (p + 1) / 2;
  }
  else return -1;
}

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