제출 #1197051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197051		YassirSalama	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	24 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){
	return (c=='A'?0:(c=='T'?1: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, 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]||m[1][0]+m[1][2]!=m[0][1]+m[2][1]) return -1;
	for(int i = 0;i<3;i++){
		for(int j =i+1,mm;j<3;j++){
			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]));
		}
	}
	return 2*b+a;
}

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