Submission #1178785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178785		rayan_bd	Mutating DNA (IOI21_dna)	C++20	0 / 100	18 ms	4416 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;

#define fi first
#define se second

const int mxN = 2e5+10;


map<char,int> mp;
int n,same[mxN],prefA[mxN][2],prefB[mxN][2];
string A,B;

void init(string a,string b){
	A=a,B=b;
	n=a.size();
	same[0]=a[0]==b[0];
	mp['A']=0,mp['T']=1;
	for(int i=1;i<n;++i){
		same[i]=same[i-1]+(a[i]==b[i]);
	}
	for(int i=0;i<n;++i){
		prefA[i][mp[A[i]]]=1;
		prefB[i][mp[B[i]]]=1;
		if(i>0){
			prefA[i][0]+=prefA[i-1][0];
			prefA[i][1]+=prefA[i-1][1];
			prefB[i][0]+=prefB[i-1][0];
			prefB[i][1]+=prefB[i-1][1];
		}
	}
}

bool ok(int l,int r){
	int prefaA=prefA[l-(l!=0)][0];
	int prefaT=prefA[l-(l!=0)][1];
	int act_aA=prefA[r][0]-prefaA;
	int act_aT=prefA[r][1]-prefaT;


	int prefbA=prefB[l-(l!=0)][0];
	int prefbT=prefB[l-(l!=0)][1];
	int act_bA=prefB[r][0]-prefbA;
	int act_bT=prefB[r][1]-prefbT;

	if(act_aA!=act_bA||act_aT!=act_bT) return 0;
	return 1;
}

int qry(int l,int r){
	if(l==0) return same[r];
	return same[r]-same[l-1];
}

int get_distance(int l,int r){
	if(qry(l,r)==(r-l+1)) return 0;
	if(!ok(l,r)) return -1;
	return qry(l,r)/2;
}

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