Submission #441080

#	Time	Username	Problem	Language	Result	Execution time	Memory
441080		MetalPower	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	8448 KiB

dna

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

#include "dna.h"

const int MX = 1e5 + 10;

map<char, int> mp;
int pref[MX][3][3], sum[MX][3][2];

void init(string a, string b){
	int N = a.length();

	mp['A'] = 0;
	mp['T'] = 1;
	mp['C'] = 2;

	for(int i = 0; i < N; i++){

		sum[i + 1][mp[a[i]]][0]++;
		sum[i + 1][mp[b[i]]][1]++;
		pref[i + 1][mp[a[i]]][mp[b[i]]]++;

		for(int j = 0; j < 3; j++)
			for(int k = 0; k < 3; k++)
				pref[i + 1][j][k] += pref[i][j][k];

		for(int j = 0; j < 3; j++){
			sum[i + 1][j][0] += sum[i][j][0];
			sum[i + 1][j][1] += sum[i][j][1];
		}
	}
}

int d(int a, int b){
	return a > b ? a - b : b - a;
}

int arr[3][3];

int get_distance(int x, int y){
	for(int j = 0; j < 3; j++)
		if(sum[y + 1][j][0] - sum[x][j][0] != sum[y + 1][j][1] - sum[x][j][1]) return -1;

	for(int j = 0; j < 3; j++)
		for(int k = 0; k < 3; k++)
			arr[j][k] = pref[y + 1][j][k] - pref[x][j][k];

	int ans = 0;

	ans += min(arr[0][2], arr[2][0]);
	ans += min(arr[0][1], arr[1][0]);
	ans += min(arr[1][2], arr[2][1]);

	if(d(arr[0][2], arr[2][0]) != d(arr[0][1], arr[1][0]) || d(arr[0][1], arr[1][0]) != d(arr[1][2], arr[2][1]))
		return -1;

	ans += 2 * d(arr[0][2], arr[2][0]);

	return ans;
}

/*
int main(){
	int N, Q; scanf("%d %d", &N, &Q);
	string a, b; a.resize(N, '_'); b.resize(N, '_');
	for(int i = 0; i < N; i++) scanf(" %c", &a[i]);
	for(int i = 0; i < N; i++) scanf(" %c", &b[i]);
	init(a, b);
	for(int i = 0; i < Q; i++){
		int l, r; scanf("%d %d", &l, &r);
		printf("%d\n", get_distance(l, r));
	}
}
*/

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