Submission #623848

#	Time	Username	Problem	Language	Result	Execution time	Memory
623848		Alma	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	7232 KiB

dna

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

#define fi first
#define se second
using ll = long long;
using ii = pair<int,int>;

const int INF = 1e9;
const ll LLINF = 1e18;
using vi = vector<int>;
using vvi = vector<vi>;

struct dna {
	int ac, at, ca, ct, ta, tc;
};

int n;
vector<dna> pos, pre;

void init (string a, string b) {
	n = a.size();
	pos = vector<dna>(n);
	for (int i = 0; i < n; i++) {
		if (a[i] == 'A' and b[i] == 'C') pos[i].ac = 1;
		if (a[i] == 'A' and b[i] == 'T') pos[i].at = 1;
		if (a[i] == 'C' and b[i] == 'A') pos[i].ca = 1;
		if (a[i] == 'C' and b[i] == 'T') pos[i].ct = 1;
		if (a[i] == 'T' and b[i] == 'A') pos[i].ta = 1;
		if (a[i] == 'T' and b[i] == 'C') pos[i].tc = 1;
	}
	pre = vector<dna>(n+1);
	pre[0].ac = pre[0].at = pre[0].ca = pre[0].ct = pre[0].ta = pre[0].tc = 0;
	for (int i = 0; i < n; i++) {
		pre[i+1].ac = pre[i].ac + pos[i].ac;
		pre[i+1].at = pre[i].at + pos[i].at;
		pre[i+1].ca = pre[i].ca + pos[i].ca;
		pre[i+1].ct = pre[i].ct + pos[i].ct;
		pre[i+1].ta = pre[i].ta + pos[i].ta;
		pre[i+1].tc = pre[i].tc + pos[i].tc;
	}
}

int get_distance (int x, int y) {
	y++;
	int AC = pre[y].ac - pre[x].ac;
	int AT = pre[y].at - pre[x].at;
	int CA = pre[y].ca - pre[x].ca;
	int CT = pre[y].ct - pre[x].ct;
	int TA = pre[y].ta - pre[x].ta;
	int TC = pre[y].tc - pre[x].tc;
	
	int ans = 0, res;
	res = min(AC, CA);
	ans += res;
	AC -= res; CA -= res;
	res = min(AT, TA);
	ans += res;
	AT -= res; TA -= res;
	res = min(CT, TC);
	ans += res;
	CT -= res; TC -= res;
	if (AC == CT and CT == TA) {
		ans += 2*AC;
		AC = CT = TA = 0;
	}
	if (AT == TC and TC == CA) {
		ans += 2*AT;
		AT = TC = CA = 0;
	} 

	if (AC + AT + CA + CT + TA + TC > 0) return -1;
	return ans;
}

// int main() {
// 	init("ATACAT", "ACTATA");
// 	cout << get_distance(1, 3) << '\n';
// }

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