Submission #1057320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1057320		mariaclara	Mutating DNA (IOI21_dna)	C++17	100 / 100	21 ms	6288 KiB

dna

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

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define mk make_pair
#define fr first
#define sc second

int n;
vector<int> pref[6];
void init(string a, string b) {
	n = sz(a);

	for(int i = 0; i < 6; i++) pref[i].resize(n+1);

	for(int i = 0; i < n; i++) {
		for(int j = 0; i > 0 and j < 6; j++) pref[j][i+1] = pref[j][i];
		if(a[i] == 'C' and b[i] == 'A') pref[0][i+1]++;
		if(a[i] == 'C' and b[i] == 'T') pref[1][i+1]++;
		if(a[i] == 'A' and b[i] == 'T') pref[2][i+1]++;
		if(a[i] == 'T' and b[i] == 'A') pref[3][i+1]++;
		if(a[i] == 'T' and b[i] == 'C') pref[4][i+1]++;
		if(a[i] == 'A' and b[i] == 'C') pref[5][i+1]++;
	}
}

int get_distance(int x, int y) {
	int ans = 0;
	int v[6];

	for(int i = 0; i < 6; i++)
		v[i] = pref[i][y+1] - pref[i][x];

	if(v[0] + v[1] != v[4] + v[5]) return -1;
	if(v[2] + v[5] != v[0] + v[3]) return -1;
	if(v[3] + v[4] != v[1] + v[2]) return -1;

	for(int i = 0; i < 3; i++) {
		ans += min(v[i], v[5-i]);
		v[i] = abs(v[i] - v[5-i]);
	}

	return ans + 2*v[0];
}

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