Submission #1245540

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245540		andrej246	Mutating DNA (IOI21_dna)	C++20	100 / 100	29 ms	11336 KiB

dna

#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;

#define FOR(i,n) for (long long i = 0; i < (n); i++)
#define FORS(i,s,n) for (long long i = (s); i < (n); i++)
#define FORR(i,n) for (long long i = (n)-1; i >= 0; i--)
#define NL '\n'
#define EL cout << NL
#define PRINTV(v) for (auto a: v) {cout << a << " ";} EL;
#define PRINTVV(v) for (auto a: v) {PRINTV(a);}
#define f first
#define s second
#define all(v) (v).first(), (v).second()

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<vpl> vvpl;

vvpl psum;

void init(std::string a, std::string b) {
	ll n = a.size();
	psum.assign(n,vpl(3,{0,0}));
	vpl cur(3,{0,0});
	FOR(i,n) {
		if (a[i] == 'A' && b[i] == 'T') cur[0].f++;
		if (a[i] == 'T' && b[i] == 'A') cur[0].s++;
		if (a[i] == 'T' && b[i] == 'C') cur[1].f++;
		if (a[i] == 'C' && b[i] == 'T') cur[1].s++;
		if (a[i] == 'C' && b[i] == 'A') cur[2].f++;
		if (a[i] == 'A' && b[i] == 'C') cur[2].s++;
		psum[i] = cur;
	}
}

int get_distance(int x, int y) {
	vpl cnt(3,{0,0});
	FOR(k,3) {
		cnt[k].f += psum[y][k].f;
		cnt[k].s += psum[y][k].s;
		if (x > 0) {
			cnt[k].f -= psum[x-1][k].f;
			cnt[k].s -= psum[x-1][k].s;
		}
	}
	bool ok = true;
	if (cnt[0].s+cnt[2].f != cnt[0].f+cnt[2].s) ok = false;
	if (cnt[1].s+cnt[0].f != cnt[1].f+cnt[0].s) ok = false;
	if (cnt[2].s+cnt[1].f != cnt[2].f+cnt[1].s) ok = false;
	if (!ok) return -1;
	ll ans = 0;
	FOR(k,3) {
		if (cnt[k].s > cnt[k].f) swap(cnt[k].s,cnt[k].f);
		ans += cnt[k].s;
		cnt[k].f -= cnt[k].s;
	}
	ans += 2*cnt[0].f;

	return ans;
}

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