Submission #1236969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236969		i_love_mriti	Mutating DNA (IOI21_dna)	C++20	71 / 100	1595 ms	2376 KiB

dna

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

const int mxN = 2e5 + 1000;

string A, B;

void init(string a, string b){
	A = a, B = b;
}

int get_distance(int x, int y){
	int a = 0, c = 0, t = 0, good = 0, at = 0, ta = 0, ac = 0, ca = 0, tc = 0, ct = 0;
	for(int i = x; i <= y; ++i){
		a += A[i] == 'A';
		a -= B[i] == 'A';
		c += A[i] == 'C';
		c -= B[i] == 'C';
		t += A[i] == 'T';
		t -= B[i] == 'T';
		if(A[i] == 'A' && B[i] == 'T') ++at;
		else if(A[i] == 'T' && B[i] == 'A') ++ta;
		else if(A[i] == 'A' && B[i] == 'C') ++ac;
		else if(A[i] == 'C' && B[i] == 'A') ++ca;
		else if(A[i] == 'C' && B[i] == 'T') ++ct;
		else if(A[i] == 'T' && B[i] == 'C') ++tc;
		else ++good;
	}
	if(a == 0 && c == 0 && t == 0){
		if(good == (y - x + 1)) return 0;
		int hehehe = ((y - x + 1) - min(at, ta) * 2 - min(ac, ca) * 2 - min(tc, ct) * 2 - good), one = 1, moves = 0;
		while(hehehe > 0){
			if(one == 1) --hehehe;
			else hehehe -= 2;
			one = 1 - one;
			++moves;
		}
		return min(at, ta) + min(ac, ca) + min(tc, ct) + moves;
	}else{
		return -1;
	}
}

/*int main(){
	#ifndef ONLINE_JUDGE
	freopen("inp.in", "r", stdin);
	freopen("output.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0);
	cin.tie(nullptr); cout.tie(nullptr);

	init("ACTCAT", "TACACT");

	cout << get_distance(0, 5) << endl;

	return 0;
}*/

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