Submission #834101

#	Time	Username	Problem	Language	Result	Execution time	Memory
834101		Abrar_Al_Samit	Mutating DNA (IOI21_dna)	C++17	100 / 100	36 ms	6920 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;


const int nax = 100000;
int a[nax], b[nax];

int cnt[nax][6]; //01, 02, 10, 12, 20, 21
int opp[] = {2, 4, 0, 5, 1, 3};
int n;

void init(string s, string t) {
	n = s.size();
	for(int i=0; i<n; ++i) {
		if(s[i]=='A') a[i] = 0;
		else if(s[i]=='T') a[i] = 1;
		else a[i] = 2;

		if(t[i]=='A') b[i] = 0;
		else if(t[i]=='T') b[i] = 1;
		else b[i] = 2;
	}
	for(int i=0; i<n; ++i) {
		if(a[i]!=b[i]) {
			if(a[i]==0) {
				if(b[i]==1) cnt[i][0] = 1;
				else cnt[i][1] = 1;
			} else if(a[i]==1) {
				if(b[i]==0) cnt[i][2] = 1;
				else cnt[i][3] = 1;
			} else {
				if(b[i]==0) cnt[i][4] = 1;
				else cnt[i][5] = 1;
			}
		}
		if(!i) continue;
		for(int j=0; j<6; ++j) {
			cnt[i][j] += cnt[i-1][j];
		}
	}
}

int get_distance(int l, int r) {
	int cur[6];
	for(int j=0; j<6; ++j) {
		cur[j] = cnt[r][j] - (l ? cnt[l-1][j] : 0);
	}
	int ans = 0;
	for(int j=0; j<6; ++j) {
		int sub = min(cur[j], cur[opp[j]]);
		cur[j] -= sub;
		cur[opp[j]] -= sub;
		ans += sub;
	}

	if(cur[0] && cur[1]) return -1;
	if(cur[2] && cur[3]) return -1;
	if(cur[4] && cur[5]) return -1;

	int m[3] = {cur[0]+cur[1], cur[2]+cur[3], cur[4]+cur[5]};
	if(m[0]!=m[1] || m[1]!=m[2]) return -1;
	ans += m[0] * 2;
	return ans;
}

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