Submission #556341

#	Time	Username	Problem	Language	Result	Execution time	Memory
556341		ddy888	Mutating DNA (IOI21_dna)	C++17	100 / 100	55 ms	10576 KiB

dna

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef tuple<int,int,int> ti;  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#include "dna.h"

const int MAXN = 100010;
int n, a[MAXN], b[MAXN];
map<char, int> idx = {{'A',0},{'T',1},{'C',2}};

int acnt[MAXN][3];
int bcnt[MAXN][3];
int pd[MAXN][3][3]; 
int td[MAXN][3][3][3];

int sum(int qs, int qe, int ida, int idb) {
	return pd[qe][ida][idb] - pd[qs - 1][ida][idb];
}

void init(std::string A, std::string B) {
	n = A.size();
	for (int i = 1; i <= n; ++i) {
		a[i] = idx[A[i - 1]];
		b[i] = idx[B[i - 1]];
	}
	for (int i = 1; i <= n; ++i) {
		++acnt[i][a[i]];
		++bcnt[i][b[i]];
		for (int j = 0; j < 3; ++j) {
			acnt[i][j] += acnt[i - 1][j];
			bcnt[i][j] += bcnt[i - 1][j];
		}

		if (a[i] != b[i]) 
			++pd[i][a[i]][b[i]];
		for (int j = 0; j < 3; ++j) 
			for (int k = 0; k < 3; ++k) 
				pd[i][j][k] += pd[i - 1][j][k];
	}
}

int get_distance(int x, int y) {
	++x, ++y;
	for (int i = 0; i < 3; ++i) 
		if (acnt[y][i] - acnt[x - 1][i] != bcnt[y][i] - bcnt[x - 1][i])
			return -1;

	int atta = min(sum(x, y, 0, 1), sum(x, y, 1, 0));
	int acca = min(sum(x, y, 0, 2), sum(x, y, 2, 0));
	int tcct = min(sum(x, y, 1, 2), sum(x, y, 2, 1));
	return atta + acca + tcct + abs(max(sum(x, y, 0, 1), sum(x, y, 1, 0)) - atta) * 2;
}

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