Submission #1228330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228330		bornag	Mutating DNA (IOI21_dna)	C++20	56 / 100	46 ms	58116 KiB

dna

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

#define ll long long

const int MAXN = 1e5 + 7;

ll pref[MAXN][7][10];
ll same[MAXN];

void init(string a, string b) {
	
	for(ll i = 0; i < a.size(); i++) {
		for(ll j = 0; j < 2; j++)
			for(ll k = 0; k < 3; k++)
				pref[i + 1][j][k] += pref[i][j][k];
				
		pref[i + 1][1][(b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2))]++;
		pref[i + 1][0][(a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2))]++;
		same[i + 1] = same[i] + !(a[i] == b[i]);
	}
}

int get_distance(int x, int y) {
	x++, y++;
	if(pref[y][1][0] - pref[x - 1][1][0] != pref[y][0][0] - pref[x - 1][0][0]
		|| pref[y][1][1] - pref[x - 1][1][1] != pref[y][0][1] - pref[x - 1][0][1]
		|| pref[y][1][2] - pref[x - 1][1][2] != pref[y][0][2] - pref[x - 1][0][2])
			return -1;
	
	return (same[y] - same[x - 1]) / 2LL + ((same[y] - same[x - 1]) % 2LL);
}

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