Submission #1128892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128892		aguss	Mutating DNA (IOI21_dna)	C++20	100 / 100	32 ms	6412 KiB

dna

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

#define _USE_MATH_DEFINES
#define INF LLONG_MAX
#define MOD 1000000007

#define endl "\n"
#define sp " "

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

#define f1(i, x) for(auto &i : x)
#define f2(i, x, j) for(ll i = j; i < x; i++)

#define raya() cout << endl << "====================================" << endl
#define dbg(x) cerr << #x << ": " << x << endl;

using namespace std;
using ll = long long;
vector<int> a, t, c, ac, ca, ta, ct, at, tc;
vector<int> diff;
void init(string x, string y) {
	int n = x.size();
	a.assign(n + 1, 0);
	t.assign(n + 1, 0);
	c.assign(n + 1, 0);
	at.assign(n + 1, 0);
	ac.assign(n + 1, 0);
	tc.assign(n + 1, 0);
	ta.assign(n + 1, 0);
	ca.assign(n + 1, 0);
	ct.assign(n + 1, 0);
	diff.assign(n + 1, 0);
	diff.assign(n + 1, 0);
	for(int i = 0; i < n; i++){
		if(x[i] == 'A') a[i + 1]++;
		if(x[i] == 'T') t[i + 1]++;
		if(x[i] == 'C') c[i + 1]++;
		if(y[i] == 'A') a[i + 1]--;
		if(y[i] == 'T') t[i + 1]--;
		if(y[i] == 'C') c[i + 1]--;
		if(x[i] == 'A' and y[i] == 'T') at[i + 1]++;
		if(x[i] == 'A' and y[i] == 'C') ac[i + 1]++;
		if(x[i] == 'T' and y[i] == 'C') tc[i + 1]++;
		if(y[i] == 'A' and x[i] == 'T') ta[i + 1]++;
		if(y[i] == 'A' and x[i] == 'C') ca[i + 1]++;
		if(y[i] == 'T' and x[i] == 'C') ct[i + 1]++;
		if(x[i] != y[i]) diff[i + 1]++;
		a[i + 1] += a[i];
		t[i + 1] += t[i];
		c[i + 1] += c[i];
		diff[i + 1] += diff[i];
		at[i + 1] += at[i];
		ac[i + 1] += ac[i];
		tc[i + 1] += tc[i];
		ta[i + 1] += ta[i];
		ca[i + 1] += ca[i];
		ct[i + 1] += ct[i];
	}
}

int get_distance(int x, int y){
	bool z = 1;
	x++;
	y++;
	if(a[y] - a[x - 1]){
		z = 0;
	}
	if(t[y] - t[x - 1]){
		z = 0;
	}
	if(c[y] - c[x - 1]){
		z = 0;
	}
	if(!z){
		return -1;
	}
	int n = diff[y] - diff[x - 1], ans = 0;
	int mat, mac, mtc;
	mat = min(at[y] - at[x - 1], ta[y] - ta[x - 1]);
	mac = min(ac[y] - ac[x - 1], ca[y] - ca[x - 1]);
	mtc = min(tc[y] - tc[x - 1], ct[y] - ct[x - 1]);
	n -= 2 * (mat + mac + mtc);
	ans += mat + mac + mtc; 
	return n / 3 * 2 + ans;
}

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