Submission #994556

#	Time	Username	Problem	Language	Result	Execution time	Memory
994556		ducksaysquack	Mutating DNA (IOI21_dna)	C++17	56 / 100	28 ms	6184 KiB

dna

#include <bits/stdc++.h>
using namespace std;
char c[3] = {'A','C','T'};
vector<vector<int>> v(3), w(3);
vector<int> p;
void init(string a, string b) {
	int n = a.size();
	for(int i=0;i<3;i++) v[i].resize(n+1), w[i].resize(n+1);
	p.resize(n+1);
	for(int i=0;i<n;i++) for(int j=0;j<3;j++) v[j][i+1] = (a[i]==c[j])+v[j][i], w[j][i+1] = (b[i]==c[j])+w[j][i];
	for(int i=0;i<n;i++) p[i+1] = p[i]+(a[i]!=b[i]);
}
int get_distance(int x, int y) {
	bool yes = true;
	for(int i=0;i<3;i++) if(v[i][y+1]-v[i][x] != w[i][y+1]-w[i][x]) yes = false;
	if(yes) return (p[y+1]-p[x]+1)/2;
	else return -1;
}

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