제출 #484622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484622		MrDeboo	DNA 돌연변이 (IOI21_dna)	C++17	21 / 100	27 ms	5200 KiB

dna

#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
string a,b;
int n;
int pre[100000];
int g[2][3][100000];
void init(std::string A, std::string B) {
	a=A;
	b=B;
	n=a.size();
	for(int i=0;i<2;i++){
		for(int w=0;w<3;w++){
			g[i][w][0]=0;
		}
	}
	for(int i=0;i<n;i++){
		pre[i]=(a[i]!=b[i]);
		if(i){
			pre[i]+=pre[i-1];
			for(int w=0;w<6;w++)g[w%2][w%3][i]=g[w%2][w%3][i-1];
		}
		g[0][(a[i]=='A'?0:1+(a[i]=='T'))][i]++;
		g[1][(b[i]=='A'?0:1+(b[i]=='T'))][i]++;
	}
}

int get_distance(int l, int r) {
	return ((g[0][1][r]-(l?g[0][1][l-1]:0)!=g[1][1][r]-(l?g[1][1][l-1]:0)||g[0][0][r]-(l?g[0][0][l-1]:0)!=g[1][0][r]-(l?g[1][0][l-1]:0)||(g[0][2][r]-(l?g[0][2][l-1]:0)!=g[1][2][r]-(l?g[1][2][l-1]:0)))?-1:((pre[r]-(l?pre[l-1]:0))/3)*2+((pre[r]-(l?pre[l-1]:0))%3!=0));
}
//AACATT
//AATCAC

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