Submission #1263281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263281		wedonttalkanymore	Mutating DNA (IOI21_dna)	C++20	100 / 100	33 ms	7688 KiB

dna

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

//#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 2e5 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 16;

int pfs[N][3], pfs1[N][3];
int same[N];
int exist[N][3], exist1[N][3];

void init(string a, string b) {
	int n = a.size();
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < 3; j++) {
			exist[i][j] = exist[i - 1][j];
			exist1[i][j] = exist1[i - 1][j];
			pfs[i][j] = pfs[i - 1][j];
			pfs1[i][j] = pfs1[i - 1][j];
		}
		same[i] = same[i - 1] + (a[i - 1] == b[i - 1]);
		
		exist[i][0] += (a[i - 1] == 'A');
		exist[i][1] += (a[i - 1] == 'T');
		exist[i][2] += (a[i - 1] == 'C');
		
		exist1[i][0] += (b[i - 1] == 'A');
		exist1[i][1] += (b[i - 1] == 'T');
		exist1[i][2] += (b[i - 1] == 'C');
		
		if (a[i - 1] != b[i - 1]) {
			string s = "";
			s += a[i - 1];
			s += b[i - 1];
			if (s == "AT") pfs[i][0]++;
			if (s == "AC") pfs[i][1]++;
			if (s == "TC") pfs[i][2]++;
			if (s == "TA") pfs1[i][0]++;
			if (s == "CA") pfs1[i][1]++;
			if (s == "CT") pfs1[i][2]++;
		}
	}
}

int get_distance(int x, int y) {
	x++; y++;
	vector <int> val(3, 0), rval(3, 0);
	for (int j = 0; j < 3; j++) {
		int v1 = exist[y][j] - exist[x - 1][j];
		int v2 = exist1[y][j] - exist1[x - 1][j];
		if (v1 != v2) return -1;
	}
	int have = same[y] - same[x - 1]; // so vi tri trung nhau
	for (int i = 0; i < 3; i++) {
		val[i] = pfs[y][i] - pfs[x - 1][i];
		rval[i] = pfs1[y][i] - pfs1[x - 1][i]; // so cap vi tri trung
	}
	int need = y - x + 1 - have; // so vi tri can hoan doi
	int sum = 0; // so buoc toi thieu
//	cout << "now: " << need << ' ' << sum << '\n';
	for (int i = 0; i < 3; i++) {
		int del = min(val[i], rval[i]);
//		cout << "at: " << del << '\n';
		need -= del * 2;
		sum += del;
	}
	sum += (2 * need) / 3;
	return sum;
}
//int main() {
//	int n, q;
//	assert(scanf("%d %d", &n, &q) == 2);
//	char A[n+1], B[n+1];
//	assert(scanf("%s", A) == 1);
//	assert(scanf("%s", B) == 1);
//	std::string a = std::string(A);
//	std::string b = std::string(B);
//	std::vector<int> x(q), y(q);
//	for (int i = 0; i < q; i++) {
//		assert(scanf("%d %d", &x[i], &y[i]) == 2);
//	}
//	fclose(stdin);
//	std::vector<int> results(q);
//	init(a, b);
//	for (int i = 0; i < q; i++) {
//		results[i] = get_distance(x[i], y[i]);
//	}
//	for (int i = 0; i < q; i++) {
//		printf("%d\n", results[i]);
//	}
//	fclose(stdout);
//	return 0;
//}

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