Submission #829258

#	Time	Username	Problem	Language	Result	Execution time	Memory
829258		fatemetmhr	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	6100 KiB

dna

// Be Name Khoda //


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

using namespace std;

#define MAX(x, y)  ((x) > (y) ? (x) : (y))
#define MIN(x, y)  ((x) < (y) ? (x) : (y))
#define debug(x)   cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)     (x).begin(), (x).end()
#define fi         first
#define se         second
#define mp         make_pair

typedef long long ll;

const int maxn5 = 1e5 + 10;

int n, ps[maxn5][3][3], cnt[3][3];

int get_ps(int l, int r, int i, int j){
	return ps[r][i][j] - (l ? ps[l - 1][i][j] : 0);
}

int get_num(int ty, int l, int r, int x){
	if(ty)
		return get_ps(l, r, 0, x) + get_ps(l, r, 1, x) + get_ps(l, r, 2, x);
	return get_ps(l, r, x, 0) + get_ps(l, r, x, 1) + get_ps(l, r, x, 2);
}



void init(std::string a, std::string b) {
	n = a.size();
	for(int i = 0; i < n; i++){
		int x = a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2);
		int y = b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2);
		if(i){
			for(int j = 0; j < 3; j++) for(int k = 0; k < 3; k++)
				ps[i][j][k] = ps[i - 1][j][k];
		}
		ps[i][x][y]++;
	}
}

int get_distance(int x, int y) {
	for(int i = 0; i < 3; i++){
		int num1 = get_num(0, x, y, i);
		int num2 = get_num(1, x, y, i);
		if(num1 != num2)
			return -1;
	}
	memset(cnt, 0, sizeof cnt);
	for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++)
		cnt[i][j] = get_ps(x, y, i, j);
	int eq = cnt[0][0] + cnt[1][1] + cnt[2][2];
	int pr = 0;
	for(int i = 0; i < 3; i++) for(int j = i + 1; j < 3; j++)
		pr += min(cnt[i][j], cnt[j][i]);
	return pr + (y - x + 1 - eq - pr * 2) / 3 * 2;
}

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