Submission #1030036

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030036		Andrey	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	7776 KiB

dna

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

int pr[100001][9];

void init(string a, string b) {
	int n = a.size();
	vector<int> haha(n+1);
	vector<int> bruh(n+1);
	for(int i = 0; i <= n; i++) {
		for(int j = 0; j < 9; j++) {
			pr[i][j] = 0;
		}
	}
	for(int i = 1; i <= n; i++) {
		if(a[i-1] == 'A') {
			haha[i] = 0;
		}
		else if(a[i-1] == 'C') {
			haha[i] = 1;
		}
		else {
			haha[i] = 2;
		}
		if(b[i-1] == 'A') {
			bruh[i] = 0;
		}
		else if(b[i-1] == 'C') {
			bruh[i] = 1;
		}
		else {
			bruh[i] = 2;
		}
		pr[i][haha[i]*3+bruh[i]]++;
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 9; j++) {
			pr[i][j]+=pr[i-1][j];
		}
	}
}

int get_distance(int x, int y) {
	y++;
	vector<int> wow(9);
	int ans = 0;
	for(int i = 0; i < 9; i++) {
		wow[i] = pr[y][i]-pr[x][i];
	}
	if(wow[0]+wow[1]+wow[2] != wow[0]+wow[3]+wow[6]) {
		return -1;
	}
	if(wow[3]+wow[4]+wow[5] != wow[1]+wow[4]+wow[7]) {
		return -1;
	}
	int a = min(wow[1],wow[3]);
	ans+=a;
	wow[1]-=a;
	wow[3]-=a;
	a = min(wow[2],wow[6]);
	ans+=a;
	wow[2]-=a;
	wow[6]-=a;
	a = min(wow[5],wow[7]);
	ans+=a;
	wow[5]-=a;
	wow[7]-=a;
	if(wow[1] > 0) {
		ans+=2*wow[1];
	}
	else {
		ans+=2*wow[3];
	}
	return ans;
}

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