Submission #1108246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108246		Newtonabc	Mutating DNA (IOI21_dna)	C++17	56 / 100	29 ms	5008 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int prea[N],preb[N],pre[N];
string tmpa,tmpb;
void init(std::string a, std::string b) {
	int n=a.size();
	tmpa=a,tmpb=b;
	prea[0]=(a[0]=='A'),preb[0]=(b[0]=='A');
	for(int i=1;i<n;i++) prea[i]=prea[i-1]+(a[i]=='A'),preb[i]=preb[i-1]+(b[i]=='A');
	pre[0]=(a[0]!=b[0]);
	for(int i=1;i<n;i++) pre[i]=pre[i-1]+(a[i]!=b[i]);
	/*for(int i=0;i<n;i++) cout<<pre[i] <<" ";
	cout<<'\n';*/
}

int get_distance(int x, int y) {
	if(y-x<=2){
		int aa=0,at=0,ag=0,ba=0,bt=0,bg=0;
		for(int i=x;i<=y;i++){
			if(tmpa[i]=='A') aa++;
			if(tmpa[i]=='T') at++;
			if(tmpa[i]=='G') ag++;
			if(tmpb[i]=='A') ba++;
			if(tmpb[i]=='T') bt++;
			if(tmpb[i]=='G') bg++;
		}
		if((aa==ba && at==bt && ag==bg)==0) return -1;
		bool b=true;
		for(int i=x;i<=y;i++) if(tmpa[i]!=tmpb[i]) b=false;
		if(b) return 0;
		int cnt=0;
		for(int i=x;i<=y;i++) if(tmpa[i]!=tmpb[i]) cnt++;
		if(cnt==3) return 2;
		else return 1;
	}
	if(prea[y]-(x-1>=0?prea[x-1]:0)==preb[y]-(x-1>=0?preb[x-1]:0)) return (pre[y]-(x-1>=0?pre[x-1]:0))/2;
	return -1;
}

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