제출 #1048875

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1048875		DorostWef	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	24 ms	7780 KiB

dna

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

using namespace std;
const int N = 100005;
string s, t;
int ps[N][3][3], n;

int f (char c) {
	return c % 3;
}

void init(std::string a, std::string b) {
	s = a;
	t = b;
	n = (int)s.size();
	for (int i = 0; i < n; i++) {
		ps[i][f(s[i])][f(t[i])]++;
		if (i) {
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					ps[i][j][k] += ps[i - 1][j][k];
				}
			}
		}
	}
}

int get_distance(int x, int y) {
	int a[3][3], b[3] = {};
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			a[i][j] = ps[y][i][j] - (x ? ps[x - 1][i][j] : 0);
			b[i] += a[i][j];
			b[j] -= a[i][j];
		}
	}
	int ans = 0;
	bool f = true;
	for (int i = 0; i < 3; i++ ){
		if (b[i] != 0)
			f = false;
		for (int j = i + 1; j < 3; j++){
			int k = min(a[i][j], a[j][i]);
			ans += k;
			a[i][j] -= k;
			a[j][i] -= k;
		}
	}
	int mn = INT_MAX, cnt = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (i != j) {
				ans += a[i][j];
				if (a[i][j]) {
					mn = min (mn, a[i][j]);
					cnt++;
				}
			}
		}
	}
	if (cnt == 3) {
		ans -= mn;
	}
	return (f ? ans : -1);
}

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