Submission #1326160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326160		SonicML	Mutating DNA (IOI21_dna)	C++20	100 / 100	27 ms	8416 KiB

dna

#include "dna.h"
#include <string>
#include <iostream>

using namespace std;

int const NMAX = 1e5;
int freq[9][1 + NMAX];
int freqA[3][1 + NMAX];
int freqB[3][1 + NMAX];

int getVal(char ch) {
  if(ch == 'A') {
    return 0;
  }else if(ch == 'C') {
    return 1;
  }else {
    return 2;
  }
}

void init(string a, string b) {
  int n = a.size();
  for(int i = 1;i <= n;i++) {
    int val = getVal(a[i-1]) * 3 + getVal(b[i-1]);
    for(int k = 0;k < 9;k++) {
      freq[k][i] = freq[k][i-1];
    }
    freq[val][i]++;
    for(int k = 0;k < 3;k++) {
      freqA[k][i] = freqA[k][i-1];
      freqB[k][i] = freqB[k][i-1];
    }
    freqA[getVal(a[i-1])][i]++;
    freqB[getVal(b[i-1])][i]++;
  }
}

int get_distance(int x, int y) {
  x++;
  y++;
  bool isGood = true; 
  for(int k = 0;k < 3;k++) {
    if(freqA[k][y] - freqA[k][x-1] != freqB[k][y] - freqB[k][x-1]) {
      isGood = false;
    }
  } 
  if(isGood) {
    int ans = 0;
    int split = 0;
    for(int k1 = 0;k1 < 3;k1++) {
      for(int k2 = 0;k2 < k1;k2++) {
        int val1 = k1 * 3 + k2, val2 = k2 * 3 + k1;
        ans += min(freq[val1][y]-freq[val1][x-1], freq[val2][y]-freq[val2][x-1]);
        split = max(freq[val1][y]-freq[val1][x-1], freq[val2][y]-freq[val2][x-1]) - 
                min(freq[val1][y]-freq[val1][x-1], freq[val2][y]-freq[val2][x-1]);
      }
    }
    ans += split * 2;
    return ans;
  }
	return -1;
}

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