Submission #1176524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176524		slivajan	Mutating DNA (IOI21_dna)	C++20	100 / 100	35 ms	7108 KiB

dna

#include "dna.h"

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

using un = int;
using vuc = vector<un>;
using vol = vector<bool>;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr char A = 'A';
constexpr char B = 'T';
constexpr char C = 'C';


constexpr un AB = 0;
constexpr un BA = 1;
constexpr un BC = 2;
constexpr un CB = 3;
constexpr un AC = 4;
constexpr un CA = 5;



vec<vuc> prefixes;
un N;


void init(std::string X, std::string Y) {
	N = X.size();

	vec<vuc> events(6, vuc(N, 0));

	REP(i, 0, N){
		if ((X[i] == A) and (Y[i] == B)){
			events[AB][i] = 1;
		}
		if ((X[i] == B) and (Y[i] == A)){
			events[BA][i] = 1;
		}
		if ((X[i] == A) and (Y[i] == C)){
			events[AC][i] = 1;
		}
		if ((X[i] == C) and (Y[i] == A)){
			events[CA][i] = 1;
		}
		if ((X[i] == B) and (Y[i] == C)){
			events[BC][i] = 1;
		}
		if ((X[i] == C) and (Y[i] == B)){
			events[CB][i] = 1;
		}
	}


	prefixes = vec<vuc>(6, vuc(N+1, 0));

	REP(s, 0, 6) {
		REP(i, 1, N+1){
			prefixes[s][i] = prefixes[s][i-1] + events[s][i-1];
		}
	}

}

int get_distance(int x, int y) {
	vuc rets(6, 0);

	REP(s, 0, 6){
		rets[s] = prefixes[s][y+1] - prefixes[s][x];
	}

	if ((rets[AB] + rets[AC]) != (rets[BA] + rets[CA])) return -1;
	if ((rets[BA] + rets[BC]) != (rets[AB] + rets[CB])) return -1;
	if ((rets[CA] + rets[CB]) != (rets[AC] + rets[BC])) return -1;


	un ret = 0;
	un m;


	m = min(rets[AB], rets[BA]);
	ret += m;
	rets[AB] -= m;
	rets[BA] -= m;

	m = min(rets[BC], rets[CB]);
	ret += m;
	rets[BC] -= m;
	rets[CB] -= m;

	m = min(rets[AC], rets[CA]);
	ret += m;
	rets[AC] -= m;
	rets[CA] -= m;


	ret += 2*max(rets[AB], rets[BA]);

	return ret;
}

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