Submission #440030

#	Time	Username	Problem	Language	Result	Execution time	Memory
440030		algorithm16	Mutating DNA (IOI21_dna)	C++17	100 / 100	67 ms	8752 KiB

dna

#include "dna.h"
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string a1,b1,s="ACT";
int n,cnt[3][2][100005],p[3][3][100005];
int get_cnt(int ind1,int ind2,int l,int r) {
	if(!l) return cnt[ind1][ind2][r];
	return cnt[ind1][ind2][r]-cnt[ind1][ind2][l-1];
}
int get_p(int ind1,int ind2,int l,int r) {
	if(!l) return p[ind1][ind2][r];
	return p[ind1][ind2][r]-p[ind1][ind2][l-1];
}
void init(std::string a, std::string b) {
	n=a.size();
	for(int i=0;i<n;i++) {
		for(int j=0;j<3;j++) {
			if(a[i]==s[j]) cnt[j][0][i]=1;
			if(b[i]==s[j]) cnt[j][1][i]=1;
		}
		for(int j=0;j<3;j++) {
			for(int k=0;k<2;k++) {
				if(i) cnt[j][k][i]+=cnt[j][k][i-1];
			}
		}
		for(int j=0;j<3;j++) {
			for(int k=0;k<3;k++) {
				if(j!=k && a[i]==s[j] && b[i]==s[k]) p[j][k][i]=1;
			}
		}
		for(int j=0;j<3;j++) {
			for(int k=0;k<3;k++) {
				if(i) p[j][k][i]+=p[j][k][i-1];
			}
		}
	}
	/*for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++) {
			cout << p[i][j][n-1] << " ";
		}
	}
	cout << "\n";*/
	/*for(int i=0;i<3;i++) {
		for(int j=0;j<n;j++) {
			cout << cnt[i][0][j] << " ";
		}
		cout << "\n";
	}*/
}

int get_distance(int x, int y) {
	int diffa=get_cnt(0,0,x,y)-get_cnt(0,1,x,y);
	int diffc=get_cnt(1,0,x,y)-get_cnt(1,1,x,y);
	int difft=get_cnt(2,0,x,y)-get_cnt(2,1,x,y);
	//cout << x << " " << y << " " << diffa << " " << diffc << " " << difft << "\n";
	if(diffa!=0 || diffc!=0 || difft!=0) return -1;
	int l=0,ret=0;
	for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++) {
			l+=get_p(i,j,x,y);
		}
	}
	//cout << l << "\n";
	for(int i=0;i<3;i++) {
		for(int j=i+1;j<3;j++) {
			int sum=min(get_p(i,j,x,y),get_p(j,i,x,y));
			ret+=sum;
			l-=sum*2;
		}
	}
	return ret+(l/3)*2;
}

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