Submission #816342

#	Time	Username	Problem	Language	Result	Execution time	Memory
816342		penguinman	Mutating DNA (IOI21_dna)	C++17	100 / 100	89 ms	23628 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define all(a) a.begin(), a.end()
#define pb emplace_back
#define mp std::make_pair

vector<vii> sum;
ll N;

void init(std::string a, std::string b) {
	string S = "ACT";
	N = a.size();
	sum.resize(N+1, vii(3, vi(3)));
	rep(i,0,N){
		ll l = 0, r = 0;
		rep(j,0,3){
			if(S[j] == a[i]) l = j;
		}
		rep(j,0,3){
			if(S[j] == b[i]) r = j;
		}
		rep(j,0,3){
			rep(k,0,3){
				sum[i+1][j][k] = sum[i][j][k];
			}
		}
		sum[i+1][l][r]++;
	}
}

int get_distance(int x, int y) {
	y++;
	vii num(3,vi(3));
	rep(i,0,3){
		rep(j,0,3) num[i][j] = sum[y][i][j]-sum[x][i][j];
	}
	int ans = 0;
	rep(i,0,3) num[i][i] = 0;
	rep(i,0,3){
		rep(j,i+1,3){
			ll val = std::min(num[i][j], num[j][i]);
			num[i][j] -= val;
			num[j][i] -= val;
			ans += val;
		}
	}
	if(num[0][1]+num[0][2] != num[1][0]+num[2][0]) return -1;
	if(num[1][0]+num[1][2] != num[0][1]+num[2][1]) return -1;
	if(num[2][1]+num[2][0] != num[0][2]+num[1][2]) return -1;
	ll cnt = 0;
	rep(i,0,3){
		rep(j,0,3) cnt += num[i][j];
	}
	assert(cnt%3 == 0);
	ans += cnt/3*2;
	return ans;
}

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