제출 #1034446

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

dna

#include "dna.h"

#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
ll cnt[100100][3][3];
ll cv(char x){	
	if (x=='A')return 0;
	if (x=='C')return 1;
	return 2;
}
void init(std::string a, std::string b) {
	ll n = sz(a);
	for (ll i = 0;i < n;i ++){
		if (i)for (ll j = 0;j < 3;j ++)for (ll k = 0;k < 3;k ++)cnt[i][j][k] = cnt[i-1][j][k];
		cnt[i][cv(a[i])][cv(b[i])]++;
	}
}

int get_distance(int x, int y) {
	ll tmp[3][3];
	for (ll i = 0;i < 3;i ++)for (ll j = 0;j < 3;j ++){
		tmp[i][j] = cnt[y][i][j];
		if (x)tmp[i][j] -= cnt[x-1][i][j];
	}
	for (ll i = 0;i < 3;i ++){
		if (tmp[i][0] + tmp[i][1] + tmp[i][2] != tmp[0][i] + tmp[1][i] + tmp[2][i])return -1;
	}
	ll res = 0;
	res += min(tmp[0][2],tmp[2][0]);
	res += min(tmp[0][1],tmp[1][0]);
	res += min(tmp[1][2],tmp[2][1]);
	// cout<<(max(tmp[0][2],tmp[2][0]) - min(tmp[0][2],tmp[2][0]))<<endl;
	res += (max(tmp[0][2],tmp[2][0]) - min(tmp[0][2],tmp[2][0])) * 2;
	return res;
}

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