Submission #1131801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131801		Mathias	Mutating DNA (IOI21_dna)	C++20	100 / 100	25 ms	7492 KiB

dna

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define fi first
#define sc second
#define vi vector<int>
#define pii pair<int,int>
#define vpi vector<pair<int,int> >
#define mp make_pair 
const ll MOD1 = 1e9+7;
const ll MOD2 = 998244353;
const ll MOD3 = 1e9+93;
const ll MOD4 = 1e9+97;
const int INF = 1e9+7;
const int BASE = 1<<20;
const int LOG = 20;
const int ALF = 27;
const int MAXN = 1e6+7;
const int MAXNN = 1e3+7;
int p1[3][MAXN], p2[3][MAXN], m[6][MAXN];
void init(string a,string b){
	a="%"+a, b="%"+b;
	for(int i=1;i<a.size();i++){
		for(int j=0;j<3;j++) p1[j][i]=p1[j][i-1];
		if(a[i]=='A') p1[0][i]++;
		else if(a[i]=='C') p1[1][i]++;
		else p1[2][i]++;
	} 
	for(int i=1;i<b.size();i++){
		for(int j=0;j<3;j++) p2[j][i]=p2[j][i-1];
		if(b[i]=='A') p2[0][i]++;
		else if(b[i]=='C') p2[1][i]++;
		else p2[2][i]++;
	}
	for(int i=1;i<a.size();i++){
		for(int j=0;j<6;j++) m[j][i]=m[j][i-1];
		if(a[i]=='A' and b[i]=='T') m[0][i]++;
		if(a[i]=='T' and b[i]=='A') m[1][i]++;
		if(a[i]=='C' and b[i]=='A') m[2][i]++;
		if(a[i]=='A' and b[i]=='C') m[3][i]++;
		if(a[i]=='T' and b[i]=='C') m[4][i]++;
		if(a[i]=='C' and b[i]=='T') m[5][i]++;
	} 		
}
int get_distance(int x,int y){
	x++, y++;
	int x1,x2,x3,x4,x5,x6,x7,x8,x9;
	for(int i=0;i<3;i++) if(p1[i][y]-p1[i][x-1]!=p2[i][y]-p2[i][x-1]) return -1;
	x1=m[0][y]-m[0][x-1];
	x2=m[1][y]-m[1][x-1];
	x3=m[2][y]-m[2][x-1];
	x4=m[3][y]-m[3][x-1];
	x5=m[4][y]-m[4][x-1];
	x6=m[5][y]-m[5][x-1];
	x7=max(x1,x2)-min(x1,x2);
	x8=max(x3,x4)-min(x3,x4);
	x9=max(x5,x6)-min(x5,x6);
	return min(x1,x2)+min(x3,x4)+min(x5,x6)+(2*(x7+x8+x9)/3);
}

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