Submission #1022788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022788		NeroZein	Mutating DNA (IOI21_dna)	C++17	0 / 100	24 ms	16924 KiB

dna

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

const int N = 1e5 + 5;

int t[N][3][3];
int occ[N][3][2];

int to_num(char c) {
  return (c == 'A' ? 0 : c == 'C' ? 1 : 2);
}

void init(string a, string b) {
  int n = (int) a.size(); 
  occ[0][to_num(a[0])][0] = 1;
  occ[0][to_num(b[0])][1] = 1;
  t[0][to_num(a[0])][to_num(b[0])]++;
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      occ[i][j][0] = occ[i - 1][j][0];
      occ[i][j][1] = occ[i - 1][j][1];
    }
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        t[i][j][k] = t[i - 1][j][k];
      }
    }
    occ[i][to_num(a[i])][0]++;
    occ[i][to_num(b[i])][1]++;
    t[i][to_num(a[i])][to_num(b[i])]++;
  }
}

int get_distance(int x, int y) {
  for (int j = 0; j < 3; ++j) {//check
    int occa = occ[y][j][0] - (x > 0 ? occ[x - 1][j][0] : 0);
    int occb = occ[y][j][1] - (x > 0 ? occ[x - 1][j][1] : 0);
    if (occa != occb) {
      return -1; 
    }
  }
  vector<vector<int>> tmp(3, vector<int> (3));
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      tmp[i][j] = t[y][i][j] - (x > 0 ? t[x - 1][i][j] : 0);
      //cout << "x, y, i, j, tmp: " << x << ' ' << y << ' ' << i << ' ' << j << ' ' << tmp[i][j] << endl; 
    }
  }
  int ans = 0;
  for (int i = 0; i < 3; ++i) {
    for (int j = i + 1; j < 3; ++j) {
      int mn = min(tmp[i][j], tmp[j][i]);
      tmp[i][j] -= mn;
      tmp[j][i] -= mn;
      ans += mn; 
    }
  }
  int res = 0; 
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      res += tmp[i][j]; 
    }
  }
  //cout << "ans, res: " << ans << ' ' << res << endl; 
  assert(res % 3 == 0);
  ans += res - res / 3; 
  return ans;
}

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