Submission #1170391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170391		MateiKing80	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	42 ms	6152 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> cnt[3][3];

int mp[256];

void init(string a, string b) 
{
	mp['A'] = 0; mp['T'] = 1; mp['C'] = 2;
	n = a.length();
	for (int i = 0; i != 3; i ++) 
		for (int j = 0; j != 3; j ++)
			cnt[i][j].resize(n + 1);
	for (int i = 0; i != n; i ++) 
	{
		int u = mp[a[i]], v = mp[b[i]];
		for (int j = 0; j != 3; j ++)
			for (int k = 0; k != 3; k ++)
				cnt[j][k][i + 1] = cnt[j][k][i] + (j == u && k == v);
	}
}

int get_distance(int x, int y) 
{
	int ans = 0, cyc = -1;
	for (int i = 0; i != 3; i ++) 
	{
		int j = (i + 1) % 3;
		int a = cnt[i][j][y + 1] - cnt[i][j][x];
		int b = cnt[j][i][y + 1] - cnt[j][i][x];
		
		if (i == 0) 
			cyc = a - b;
		else if (cyc != a - b) 
			return -1;
		ans += min(a, b);
	}
	return ans + 2 * abs(cyc);
}

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