Submission #1240940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240940		bornag	Mutating DNA (IOI21_dna)	C++20	100 / 100	46 ms	16392 KiB

dna

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define X first
#define Y second
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())

const ll MOD = 1e9 + 7;
const ll BASE = 32;
const int MAXN = 2e5 + 7;

int prefa[MAXN][5], prefb[MAXN][5], same[MAXN][5][5];
int n;

void init(string a, string b) {
	n = len(a);
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++)
			prefa[i][j] = prefa[i - 1][j], prefb[i][j] = prefb[i - 1][j];
			
		char let[] = {'A', 'T', 'C'};
		for(int j = 0; j < 3; j++) {
			if(a[i - 1] == let[j])
				prefa[i][j]++;
				
			if(b[i - 1] == let[j])
				prefb[i][j]++;
				 
			for(int k = 0; k < 3; k++) {
				same[i][j][k] = same[i - 1][j][k];
				if(let[k] == b[i - 1] && let[j] == a[i - 1])
					same[i][j][k]++;
			}
		}
	}
}

int get_distance(int x, int y) {
	x++, y++;
	
	for(int j = 0; j < 3; j++)
		if(prefa[y][j] - prefa[x - 1][j] != prefb[y][j] - prefb[x - 1][j])
			return -1;
	
	int c[5][5];
	for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) c[i][j] = same[y][i][j] - same[x - 1][i][j];
	
	int ret = 0;
	
	int tmp = min(c[0][1], c[1][0]);
	c[1][0] -= tmp, c[0][1] -= tmp, ret += tmp;
	
	tmp = min(c[0][2], c[2][0]);
	c[2][0] -= tmp, c[0][2] -= tmp, ret += tmp;
	
	tmp = min(c[1][2], c[2][1]);
	c[1][2] -= tmp, c[2][1] -= tmp, ret += tmp;
	
	ret += 2 * (c[1][0] + c[0][1]);
	
	return ret;
}

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