Submission #620574

#	Time	Username	Problem	Language	Result	Execution time	Memory
620574		JUANDI321	Mutating DNA (IOI21_dna)	C++17	0 / 100	39 ms	8076 KiB

dna

#include <bits/stdc++.h>

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

void init(string a, string b) 
{
	int n = a.size();
	
	aca.resize(n+2);
	ata.resize(n+2);
	ctc.resize(n+2);
	aa.resize(n+2);
	cc.resize(n+2);
	tt.resize(n+2);
	for(int i = 1; i<=n; i++)
	{
		aca[i] = aca[i-1];
		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] = ata[i-1];
		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] = ctc[i-1];
		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] = aa[i-1];
		if(a[i-1] == 'a')aa[i].first++;
		if(b[i-1] == 'a')aa[i].second++;
		tt[i] = tt[i-1];
		if(a[i-1] == 't')tt[i].first++;
		if(b[i-1] == 't')tt[i].second++;
		cc[i] = cc[i-1];
		if(a[i-1] == 'c')cc[i].first++;
		if(b[i-1] == 'c')cc[i].second++;
	}
}

int get_distance(int x, int y) 
{
	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: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16