Submission #825303

#	Time	Username	Problem	Language	Result	Execution time	Memory
825303		arnold518	Mutating DNA (IOI21_dna)	C++17	100 / 100	29 ms	6064 KiB

dna

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N, P[MAXN+10][3][3];

int f(char x)
{
	if(x=='A') return 0;
	if(x=='C') return 1;
	if(x=='T') return 2;
}

void init(string a, string b)
{
	N=a.size();
	for(int i=1; i<=N; i++)
	{
		for(int p=0; p<3; p++) for(int q=0; q<3; q++) P[i][p][q]=P[i-1][p][q];
		P[i][f(a[i-1])][f(b[i-1])]++;
	}
}

int get_distance(int l, int r) {
	l++; r++;
	int A[3][3]={{0}};
	for(int p=0; p<3; p++) for(int q=0; q<3; q++) A[p][q]=P[r][p][q]-P[l-1][p][q];
	for(int p=0; p<3; p++)
	{
		int t=0;
		for(int q=0; q<3; q++) t+=A[p][q]-A[q][p];
		if(t) return -1;
	}

	int ans=0, a;
	ans+=min(A[0][1], A[1][0]); a=abs(A[0][1]-A[1][0]);
	ans+=min(A[0][2], A[2][0]);
	ans+=min(A[2][1], A[1][2]);
	ans+=a*2;
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int f(char)':
dna.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
   18 | }
      | ^

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