Submission #1240921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240921		bornag	Mutating DNA (IOI21_dna)	C++20	56 / 100	22 ms	6916 KiB

dna

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

#define pb push_back
#define eb emplace_back
#define ppb pop_back
#define X first
#define Y second
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())

const ll MOD = 1e9 + 7;
const ll BASE = 32;
const int MAXN = 2e5 + 7;

int prefa[MAXN][5], prefb[MAXN][5], same[MAXN];
int n;

void init(string a, string b) {
	n = len(a);
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++)
			prefa[i][j] = prefa[i - 1][j], prefb[i][j] = prefb[i - 1][j];
			
		char let[] = {'A', 'T', 'C'};
		for(int j = 0; j < 3; j++) {
			if(a[i - 1] == let[j])
				prefa[i][j]++;
				
			if(b[i - 1] == let[j])
				prefb[i][j]++;
		}
		
		same[i] = same[i - 1] + (a[i - 1] != b[i - 1]);
	}
}

int ceil(int a) {
	return a / 2 + (a % 2);
}

int get_distance(int x, int y) {
	swap(x, y);
	
	for(int j = 0; j < 3; j++)
		if(prefa[x + 1][j] - prefa[y][j] != prefb[x + 1][j] - prefb[y][j])
			return -1;
	
	return ceil(same[x + 1] - same[y]);	
}

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