Submission #970136

#	Time	Username	Problem	Language	Result	Execution time	Memory
970136		elotelo966	Mutating DNA (IOI21_dna)	C++17	56 / 100	40 ms	6224 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

#define lim 100005

int n;

int pre_a_a[lim],pre_b_a[lim];// a string a char   -----  b string a char
int pre_a_t[lim],pre_b_t[lim];// a string t char   -----  b string t char
int pre_a_c[lim],pre_b_c[lim];// a string c char   -----  b string c char

int sum[lim];

inline bool querya(int x,int y){
	if(pre_a_a[y+1]-pre_a_a[x]==pre_b_a[y+1]-pre_b_a[x])return 1;
	return 0;
}

inline bool queryt(int x,int y){
	if(pre_a_t[y+1]-pre_a_t[x]==pre_b_t[y+1]-pre_b_t[x])return 1;
	return 0;
}

inline bool queryc(int x,int y){
	if(pre_a_c[y+1]-pre_a_c[x]==pre_b_c[y+1]-pre_b_c[x])return 1;
	return 0;
}

void init(string a,string b) {
	n=a.length();
	for(int i=0;i<n;i++){
		pre_a_a[i+1]=pre_a_a[i];
		if(a[i]=='A')pre_a_a[i+1]++;
		
		pre_b_a[i+1]=pre_b_a[i];
		if(b[i]=='A')pre_b_a[i+1]++;
		
		pre_a_t[i+1]=pre_a_t[i];
		if(a[i]=='T')pre_a_t[i+1]++;
		
		pre_b_t[i+1]=pre_b_t[i];
		if(b[i]=='T')pre_b_t[i+1]++;
		
		pre_a_c[i+1]=pre_a_c[i];
		if(a[i]=='C')pre_a_c[i+1]++;
		
		pre_b_c[i+1]=pre_b_c[i];
		if(b[i]=='C')pre_b_c[i+1]++;
		
		sum[i+1]=sum[i];
		if(a[i]!=b[i])sum[i+1]++;
	}
}

int get_distance(int x, int y) {
	if(y-x<=2){
		if(querya(x,y) && queryt(x,y) && queryc(x,y)){
			int tut=sum[y+1]-sum[x];
			if(tut==3)return 2;
			else if(tut==2)return 1;
			else if(tut==1)return 1;
			else return 0;
		}
		else return -1;
	}
	else{
		if(querya(x,y) && queryt(x,y)){
			return (sum[y+1]-sum[x])/2;
		}
		else return -1;
	}
}

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