Submission #620599

#	Time	Username	Problem	Language	Result	Execution time	Memory
620599		JUANDI321	Mutating DNA (IOI21_dna)	C++17	100 / 100	52 ms	8588 KiB

dna

//#include "dna_ioi.h"
#include <bits/stdc++.h>

using namespace std;
vector<pair<int, int>> aca, ata, ctc, aa, tt, cc;

void init(string a, string b) 
{
	//cout<<"alo"<<endl;
	int n = a.size();
	
	aca.resize(n+2, {0, 0});
	ata.resize(n+2, {0, 0});
	ctc.resize(n+2, {0, 0});
	aa.resize(n+2, {0, 0});
	cc.resize(n+2, {0, 0});
	tt.resize(n+2, {0, 0});
	for(int i = 1; i<=n; i++)
	{
		aca[i].first = aca[i-1].first;
		aca[i].second = aca[i-1].second;
		if(a[i-1] == 'A' && b[i-1] == 'C')aca[i].first++;
		if(a[i-1] == 'C' && b[i-1] == 'A')aca[i].second++;
		ata[i].first = ata[i-1].first;
		ata[i].second = ata[i-1].second;
		if(a[i-1] == 'A' && b[i-1] == 'T')ata[i].first++;
		if(a[i-1] == 'T' && b[i-1] == 'A')ata[i].second++;
		ctc[i].first = ctc[i-1].first;
		ctc[i].second = ctc[i-1].second;
		if(a[i-1] == 'T' && b[i-1] == 'C')ctc[i].first++;
		if(a[i-1] == 'C' && b[i-1] == 'T')ctc[i].second++;
		//
		aa[i].first = aa[i-1].first;
		aa[i].second = aa[i-1].second;
		if(a[i-1] == 'A')aa[i].first++;
		if(b[i-1] == 'A')aa[i].second++;
		tt[i].first = tt[i-1].first;
		tt[i].second = tt[i-1].second;
		if(a[i-1] == 'T')tt[i].first++;
		if(b[i-1] == 'T')tt[i].second++;
		cc[i].first = cc[i-1].first;
		cc[i].second = cc[i-1].second;
		if(a[i-1] == 'C')cc[i].first++;
		if(b[i-1] == 'C')cc[i].second++;
	}
}

int get_distance(int x, int y) 
{
	x++;
	y++;
	//cout<<aa[y].first - aa[x-1].first<<" "<<aa[y].second - aa[x-1].second<<endl;
	if(aa[y].first - aa[x-1].first == aa[y].second - aa[x-1].second && cc[y].first - cc[x-1].first == cc[y].second - cc[x-1].second && tt[y].first - tt[x-1].first == tt[y].second - tt[x-1].second)
	{
		long long ans = 0, sob = 0;
		ans+=min(aca[y].first - aca[x-1].first, aca[y].second - aca[x-1].second);
		sob+=max(aca[y].first - aca[x-1].first, aca[y].second - aca[x-1].second) - min(aca[y].first - aca[x-1].first, aca[y].second - aca[x-1].second);
		ans+=min(ata[y].first - ata[x-1].first, ata[y].second - ata[x-1].second);
		sob+=max(ata[y].first - ata[x-1].first, ata[y].second - ata[x-1].second) - min(ata[y].first - ata[x-1].first, ata[y].second - ata[x-1].second);
		ans+=min(ctc[y].first - ctc[x-1].first, ctc[y].second - ctc[x-1].second);
		sob+=max(ctc[y].first - ctc[x-1].first, ctc[y].second - ctc[x-1].second) - min(ctc[y].first - ctc[x-1].first, ctc[y].second - ctc[x-1].second);
		ans+=(sob/3)*2;
		return ans;
	}
	return -1;
}

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