Submission #1275358

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275358		crispxx	Mutating DNA (IOI21_dna)	C++20	100 / 100	27 ms	6896 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][5], 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][4] = pref[i][4];
		
		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');
		pref[i + 1][4] += (a[i] == 'C' && 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;
	
	tot_wrong -= get(1) + get(2);
	res += get(1) + get(2);
	
	// res += tot_wrong / 2;
	
	// int x1 = get(1), x3 = get(3);
	
	// int mn = min(x1, x3);
	
	// assert(x1 == x3);
	
	// x3 -= mn;
	// tot_wrong -= min(x1, x3);
	
	// res += tot_wrong / 2;
	
	// cout << "wrong: " << tot_wrong << nl;
	
	tot_wrong -= min( get(1), get(3) );
	tot_wrong -= min( get(2), get(4) );
	
	// cout << min(get(1), get(3)) << ' ' << min(get(2), get(4)) << nl;
	
	// cout << "wrong: " << tot_wrong << nl;
	
	assert(tot_wrong % 2 == 0);
	
	res += tot_wrong / 2;
	
	return res;
}

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