Submission #728881

#	Time	Username	Problem	Language	Result	Execution time	Memory
728881		NintsiChkhaidze	Mutating DNA (IOI21_dna)	C++17	100 / 100	40 ms	7152 KiB

dna

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

const int N = 1e5 + 5;
int p[N][8],a[8];
void init(string a, string b) {
	//A,C,T
	//AT - 1
	//TA - 2
	//AC - 3
	//CA - 4
	//CT - 5
	//TC - 6
	
	int n = a.size();
	for (int i = 0; i < n; i++){
		string s = ""; s+=a[i]; s+= b[i];
		int id=0;
		if (s == "AT") id=1;
		else if (s == "TA") id = 2;
		else if (s == "AC") id = 3;
		else if (s == "CA") id = 4;
		else if (s == "CT") id = 5;
		else if (s == "TC") id = 6;
		
		if (i){
			for (int d = 1; d < 7; d++)
				p[i][d] = p[i - 1][d];
		}
		p[i][id]++;
	}
}

int get_distance(int x, int y) {
	for (int d=1;d<7;d++){
		a[d] = p[y][d];
		if (x) a[d] -= p[x - 1][d]; 
	}
	
	int ans=0;
	for (int d = 1; d < 7; d+=2){
		int vl = min(a[d],a[d + 1]);
		ans += vl;
		a[d] -= vl,a[d+1]-=vl;
	}
	int mn = min({a[1],a[4],a[6]});
	ans += mn*2;
	a[1] -= mn,a[4] -= mn,a[6] -= mn;
	//146
	//ACT
	//TAC
	
	mn = min({a[2],a[3],a[5]});
	ans += mn*2;
	a[2] -= mn,a[3] -= mn,a[5] -= mn;
	
	for (int i = 1; i < 7; i++)
		if (a[i]) return -1;
	//235
	//TAC
	//ACT
	return ans;
}

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