Submission #1189641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189641		rendel	Mutating DNA (IOI21_dna)	C++20	43 / 100	1595 ms	4680 KiB

dna

#include "dna.h"
using namespace std;
const int maxn = 1e5+5;
string s1,s2;
int l1,l2;
long long int cnt;
int c1[maxn][3],c2[maxn][3];

void init(string a, string b) {
	s1=a; s2=b;
	l1=s1.length(),l2=s2.length();
	for(int i=0;i<l1;++i){
		if(s1[i]=='C') c1[i+1][0]++;
		else if(s1[i]=='A') c1[i+1][1]++;
		else if(s1[i]=='T') c1[i+1][2]++;
        for(int j=0;j<3;++j)  c1[i+1][j]+=c1[i][j];
	}
	for(int i=0;i<l2;++i){
		if(s2[i]=='C') c2[i+1][0]++;
		else if(s2[i]=='A') c2[i+1][1]++;
		else if(s2[i]=='T') c2[i+1][2]++;
        for(int j=0;j<3;++j)  c2[i+1][j]+=c2[i][j];
	}
}

int get_distance(int x, int y) {

	for(int i=0;i<3;++i){
		if(c1[y+1][i]-c1[x][i]!=c2[y+1][i]-c2[x][i]) return -1;
	}
	
	string n,m;
	for(int i=x;i<=y;++i){
		if(s1[i]!=s2[i]) { n.push_back(s1[i]); m.push_back(s2[i]); }
	}
	cnt=0;
    l1=n.length(),l2=m.length();
	for(int i=0;i<l1;++i){
		for(int j=0;j<l2;++j){
			if(n[i]==m[j] && i!=j && n[i]!=n[j] && m[i]!=m[j]){
				swap(n[i],n[j]);
				cnt++;
			}
		}
	}
	return cnt;
}

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