Submission #888865

#	Time	Username	Problem	Language	Result	Execution time	Memory
888865		allin27x	Mutating DNA (IOI21_dna)	C++17	100 / 100	28 ms	6456 KiB

dna

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

//CTA
const int N = 1e5+7;

int TC[N], AC[N], AT[N];
int CT[N], CA[N], TA[N];


void init(string A, string B){
	int n = A.size();
	for (int i=0; i<n; i++){
		TC[i+1] = TC[i] + (A[i] == 'T' && B[i] == 'C');
		AC[i+1] = AC[i] + (A[i] == 'A' && B[i] == 'C');
		AT[i+1] = AT[i] + (A[i] == 'A' && B[i] == 'T') ;
		CT[i+1] = CT[i] + (A[i] == 'C' && B[i] == 'T') ;
		CA[i+1] = CA[i] + (A[i] == 'C' && B[i] == 'A');
		TA[i+1] = TA[i] + (A[i] == 'T' && B[i] == 'A');
	}
}

int get_distance(int x, int y){
	int tc = TC[y+1] - TC[x];
	int ac = AC[y+1] - AC[x];
	int at = AT[y+1] - AT[x];
	int ct = CT[y+1] - CT[x];
	int ca = CA[y+1] - CA[x];
	int ta = TA[y+1] - TA[x];
	// cout<<tc<<' '<<ac<<' '<<at<<' '<<ct<<' '<<ca<<' '<<ta<<'\n';
	int r1 = min(tc,ct); tc-=r1, ct-=r1;
	int r2 = min(ac,ca); ca-=r2, ac-=r2;
	int r3 = min(at,ta); at-=r3, ta-=r3;

	int res = r1+r2+r3;
	if ((tc+ta != at+ct) || (ac+at != ta+ca) || (tc+ac != ca+ct)) return -1;
	res += 2*(tc+ac+at+ct+ca+ta)/3;
	return res;
}


// int main(){
// 	init("ATACAT", "ACTATA");

// 	cout<<get_distance(1,3)<<'\n';
// 	cout<<get_distance(4,5)<<'\n';
// 	cout<<get_distance(3,5)<<'\n';
// }

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