Submission #437682

#	Time	Username	Problem	Language	Result	Execution time	Memory
437682		Haunted_Cpp	Mutating DNA (IOI21_dna)	C++17	0 / 100	47 ms	6872 KiB

dna

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

const int MAX_N = 1e5 + 5;
int N;

vector<int> aA(MAX_N), aC(MAX_N), aT(MAX_N);
vector<int> bA(MAX_N), bC(MAX_N), bT(MAX_N);

vector<int> AC(MAX_N), AT(MAX_N);
vector<int> CA(MAX_N), CT(MAX_N);
vector<int> TA(MAX_N), TC(MAX_N);

void get(const string &w, vector<int> &arr, char c) {
  arr[0] = (w[0] == c);
  for (int i = 1; i < N; i++) {
    arr[i] = arr[i - 1] + (w[i] == c);
  }
}

void init(string a, string b) {
  N = a.size();
  get(a, aA, 'A');
  get(a, aC, 'C');
  get(a, aT, 'T');
  get(b, bA, 'A');
  get(b, bC, 'C');
  get(b, bT, 'T');
  for (int i = 0; i < N; i++) {
    AC[i] += (a[i] == 'A' && b[i] == 'C') + (i >= 0 ? AC[i - 1] : 0);
    AT[i] += (a[i] == 'A' && b[i] == 'T') + (i >= 0 ? AT[i - 1] : 0);
    CA[i] += (a[i] == 'C' && b[i] == 'A') + (i >= 0 ? CA[i - 1] : 0);
    CT[i] += (a[i] == 'C' && b[i] == 'T') + (i >= 0 ? CT[i - 1] : 0);
    TA[i] += (a[i] == 'T' && b[i] == 'A') + (i >= 0 ? TA[i - 1] : 0);
    TC[i] += (a[i] == 'T' && b[i] == 'C') + (i >= 0 ? TC[i - 1] : 0);
  }
}

int rq(const vector<int> &arr, int l, int r) {
  assert(l <= r);
  assert(arr[r] - (l > 0 ? arr[l - 1] : 0) >= 0);
  return arr[r] - (l > 0 ? arr[l - 1] : 0);
}

int get_distance(int x, int y) {
  if (rq(aA, x, y) != rq(bA, x, y)) return -1;
  if (rq(aC, x, y) != rq(bC, x, y)) return -1;
  if (rq(aT, x, y) != rq(bT, x, y)) return -1;
  int res = 0;
  int got = min(rq(CA, x, y), rq(AC, x, y)) + min(rq(TA, x, y), rq(AT, x, y)) + min(rq(TC, x, y), rq(CT, x, y));
  res += got;
  res += max (0, (y - x + 1) - (2 * got) - 1); 
	return res;
}

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