Submission #1197046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197046		YassirSalama	Mutating DNA (IOI21_dna)	C++17	100 / 100	25 ms	6152 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;const int maxn = 1e5+100;int pref[maxn][3][3];int g(char c){if(c=='A')return 0;else if(c=='T')return 1;else return 2;}
void init(std::string a, std::string b) {
for(int i = 0;i<a.length();i++){if(i) for(int j = 0;j<3;j++){for(int k  =0;k<3;k++){pref[i][j][k] = pref[i-1][j][k];}} pref[i][g(a[i])][g(b[i])]++;}
}
int get_distance(int x, int y) {
	int a = 0;int b = 1e9;
	int m[3][3];
	for(int i = 0;i<3;i++){
		for(int j =  0;j<3;j++){
			m[i][j] = pref[y][i][j]-(x?pref[x-1][i][j]:0);
		}
	}
	if(m[0][1]+m[0][2]!=m[1][0]+m[2][0]) return -1;
	if(m[1][0]+m[1][2]!=m[0][1]+m[2][1]) return -1;
	for(int i  =0;i<3;i++){
	}
	for(int i = 0;i<3;i++){
		for(int j =i+1;j<3;j++){
			int mm = min(m[i][j],m[j][i]);
			m[i][j]-=mm,
			m[j][i]-=mm,
			a+=mm;
		}
	}
	for(int i  =0;i<3;i++){
		for(int j  =i+1;j<3;j++){
			b = min(b,max(m[i][j],m[j][i]));
		}
	}
	// cout<<" ! "<<a<<" "<<b<<endl;
	return 2*b+a;
}

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