Submission #994570

#	Time	Username	Problem	Language	Result	Execution time	Memory
994570		ducksaysquack	Mutating DNA (IOI21_dna)	C++17	100 / 100	24 ms	6936 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, q;
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), q.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]=='A'&&b[i]!='A')+(a[i]=='T'&&b[i]=='C'), q[i+1] = q[i]+(a[i]=='A'&&b[i]=='C')-(a[i]=='C'&&b[i]=='A');
}
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]+max(q[y+1]-q[x],0);
	else return -1;
}

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