Submission #488133

#	Time	Username	Problem	Language	Result	Execution time	Memory
488133		8e7	Mutating DNA (IOI21_dna)	C++17	71 / 100	1581 ms	2960 KiB

dna

//Challenge: Accepted
#include "dna.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int s[maxn], t[maxn];
void init(string a, string b){
	int n = a.size();
	for (int i = 0;i < n;i++) {
		s[i] = (a[i] == 'A' ? 0 : (a[i] == 'T' ? 1 : 2));
		t[i] = (b[i] == 'A' ? 0 : (b[i] == 'T' ? 1 : 2));
	}
}
int get_distance(int l, int r) {
	int sc[3] = {0, 0, 0}, tc[3] = {0, 0, 0};
	int type[9];
	for (int i = 0;i < 9;i++) type[i] = 0;
	for (int i = l;i <= r;i++) {
		sc[s[i]]++, tc[t[i]]++;	
		type[s[i]*3 + t[i]]++;
	}
	if (sc[0] != tc[0] || sc[1] != tc[1] || sc[2] != tc[2]) {
		return -1;
	}
	type[0] = type[4] = type[8] = 0;	
	int p[3][2] = {{1, 3}, {2, 6}, {5, 7}};	
	int ans = 0, rem = 0;
	for (int i = 0;i < 3;i++) {
		int val = min(type[p[i][0]], type[p[i][1]]);
		type[p[i][0]] -= val;
		type[p[i][1]] -= val;
		ans += val;
		rem = max(type[p[i][0]], type[p[i][1]]);
	}
	return ans + rem * 2;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/

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