Submission #1142592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142592		draiiiiiiiiiiid	Mutating DNA (IOI21_dna)	C++20	0 / 100	20 ms	6912 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;
// #define int long long
const int MX = 2e5;
int dp[MX][6];
void init(string a, string b) {
  // string a, b; cin >> a >> b;
  int n = a.size();
  /*int dp[n+1][6];*/ memset(dp, 0, sizeof dp);
  for(int i = 1 ; i <= n ; i++) {
    dp[i][0] = dp[i-1][0] + (a[i-1] == 'T' and b[i-1] == 'A');
    dp[i][1] = dp[i-1][1] + (a[i-1] == 'T' and b[i-1] == 'C');
    dp[i][2] = dp[i-1][2] + (a[i-1] == 'A' and b[i-1] == 'C');
    dp[i][3] = dp[i-1][3] + (a[i-1] == 'A' and b[i-1] == 'T');
    dp[i][4] = dp[i-1][4] + (a[i-1] == 'C' and b[i-1] == 'T');
    dp[i][5] = dp[i-1][5] + (a[i-1] == 'C' and b[i-1] == 'A');
  }
}

int get_distance(int a, int b) {
  // int a, b; cin >> a >> b;
  // a--; b--;
  int r = 0;
  int dd[6]; memset(dd, 0, sizeof dd);
  for(int j = 0 ; j < 6 ; j++) {
    dd[j] = dp[b+1][j] - dp[a][j];
    // cout << j << " " << dd[j] << endl;
  }
  
  for(int j = 0 ; j < 3 ; j++) {
    int k = min(dd[j], dd[j+3]);
    dd[j] -= k;
    dd[j+3] -= k;
    r += k;
  }

  int s = 0;
  for(int j = 0 ; j < 6 ; j++) s += dd[j];
  r += 2*(s/3);
  // cout << r << '\n';
  return r;
}

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