Submission #1059489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059489		LittleOrange	Mutating DNA (IOI21_dna)	C++17	100 / 100	36 ms	9928 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
const string table = "ACT";
const array<string,6> mp = {"CA","AT","TC","AC","TA","CT"};
struct obj{
	string s;
	ll n;
	vector<vector<ll>> a;
	obj(){}
	obj(string S):s(S),n(S.size()),a(3,vector<ll>(s.size()+1,0)){
		for(ll i = 0;i<3;i++){
			for(ll j = 0;j<n;j++){
				a[i][j+1] = a[i][j]+(s[j]==table[i]);
			}
		}
	}
	array<ll,3> get(ll l, ll r){
		return {a[0][r+1]-a[0][l],a[1][r+1]-a[1][l],a[2][r+1]-a[2][l]};
	}
};
ll n;
string a,b;
obj oa,ob;
vector<vector<ll>> v;
void init(std::string A, std::string B) {
	n = A.size();
	a = A;
	b = B;
	oa = obj(a);
	ob = obj(b);
	v.resize(6,vector<ll>(n+1,0));
	for(ll i = 0;i<6;i++){
		for(ll j = 0;j<n;j++){
			v[i][j+1] = v[i][j]+(a[j]==mp[i][0]&&b[j]==mp[i][1]);
		}
	}
}

int get_distance(int x, int y) {
	if(oa.get(x,y)!=ob.get(x,y)) return -1;
	vector<ll> g(6,0);
	for(ll i = 0;i<6;i++) g[i] = v[i][y+1]-v[i][x];
	//for(ll i = 0;i<6;i++) cerr << g[i] << " \n"[i+1==6];
	ll ans = 0;
	for(ll i = 0;i<3;i++){
		ll h = min(g[i],g[i+3]);
		ans += h;
		g[i]-=h;
		g[i+3]-=h;
	}
	ans += g[0]*2+g[3]*2;
	return ans;
}

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