Submission #1275354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275354		crispxx	Mutating DNA (IOI21_dna)	C++20	56 / 100	21 ms	6384 KiB

dna

#include "dna.h"

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

// #define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

const int N = 1e5 + 5;

int pref[N][4], A[N][3], B[N][3];

void init(std::string a, std::string b) {
	int n = a.size();
	
	for(int j = 0; j < 3; j++) {
		pref[0][j] = 0;
		A[0][j] = 0;
		B[0][j] = 0;
	}
	
	for(int i = 0; i < n; i++) {
		
		for(int j = 0; j < 3; j++) {
			pref[i + 1][j] = pref[i][j];
			A[i + 1][j] = A[i][j];
			B[i + 1][j] = B[i][j];
		}
		
		pref[i + 1][3] = pref[i][3];
		
		pref[i + 1][0] += (a[i] != b[i]);
		pref[i + 1][1] += (a[i] == 'A' && b[i] == 'T');
		pref[i + 1][2] += (a[i] == 'A' && b[i] == 'C');
		pref[i + 1][3] += (a[i] == 'T' && b[i] == 'A');
		
		A[i + 1][0] += (a[i] == 'A');
		A[i + 1][1] += (a[i] == 'T');
		A[i + 1][2] += (a[i] == 'C');
		
		B[i + 1][0] += (b[i] == 'A');
		B[i + 1][1] += (b[i] == 'T');
		B[i + 1][2] += (b[i] == 'C');
		
	}
}

int get_distance(int x, int y) {
	y++;
	for(int j = 0; j < 3; j++) {
		if(A[y][j] - A[x][j] != B[y][j] - B[x][j]) return -1;
	}
	
	auto get = [&](int j) {
		return pref[y][j] - pref[x][j];
	};
	
	int tot_wrong = get(0), res = 0;
	
	int temp = get(1) + get(2);
	
	tot_wrong -= temp;
	res += temp;
	
	int x1 = get(1), x3 = get(3);
	
	int mn = min(x1, x3);
	
	// assert(x1 == x3);
	
	tot_wrong -= min(x1, x3);
	
	res += tot_wrong / 2;
	
	return res;
}

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