Submission #441306

#	Time	Username	Problem	Language	Result	Execution time	Memory
441306		pere_gil	Mutating DNA (IOI21_dna)	C++17	100 / 100	95 ms	16492 KiB

dna

#include "bits/stdc++.h"
#include "dna.h"
using namespace std;
 
string a,b;
vector<vector<int> > leta,letb;
// ac ca at ta ct tc
// 0  1  2  3  4  5
vector<int> contac,contca,contat,contta,contct,conttc;
 
int get_comb(char up, char down){
	if(up=='A' && down=='C') return 0;
	if(up=='C' && down=='A') return 1;
	if(up=='A' && down=='T') return 2;
	if(up=='T' && down=='A') return 3;
	if(up=='C' && down=='T') return 4;
	return 5;
}
 
int get_letter(char act){
	if(act=='A') return 0;
	if(act=='T') return 1;
	return 2;
}
 
void init(std::string A, std::string B) {
	a=A;
	b=B;
	int n=a.size();
	leta.resize(n,vector<int> (3,0));
	letb.resize(n,vector<int> (3,0));
 
	leta[0][get_letter(a[0])]++;
	letb[0][get_letter(b[0])]++;
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			leta[i][j]=leta[i-1][j];
			letb[i][j]=letb[i-1][j];
		}
		leta[i][get_letter(a[i])]++;
		letb[i][get_letter(b[i])]++;
	}

	contac.push_back(0); contca.push_back(0);
	contat.push_back(0); contta.push_back(0);
	contct.push_back(0); conttc.push_back(0);

	if(a[0]=='A' && b[0]=='C') contac[0]++;
	if(a[0]=='C' && b[0]=='A') contca[0]++;
	if(a[0]=='A' && b[0]=='T') contat[0]++;
	if(a[0]=='T' && b[0]=='A') contta[0]++;
	if(a[0]=='C' && b[0]=='T') contct[0]++;
	if(a[0]=='T' && b[0]=='C') conttc[0]++;

	for(int i=1;i<n;i++){
		contac.push_back(contac[contac.size()-1]); contca.push_back(contca[contca.size()-1]);
		contat.push_back(contat[contat.size()-1]); contta.push_back(contta[contta.size()-1]);
		contct.push_back(contct[contct.size()-1]); conttc.push_back(conttc[conttc.size()-1]);

		if(a[i]=='A' && b[i]=='C') contac[i]++;
		if(a[i]=='C' && b[i]=='A') contca[i]++;
		if(a[i]=='A' && b[i]=='T') contat[i]++;
		if(a[i]=='T' && b[i]=='A') contta[i]++;
		if(a[i]=='C' && b[i]=='T') contct[i]++;
		if(a[i]=='T' && b[i]=='C') conttc[i]++;
	}
}
 
int count_letter(bool is_a, int i, int j, int pos){
	if(is_a)
		return (i==0) ? leta[j][pos] : leta[j][pos] - leta[i-1][pos];
	return (i==0) ? letb[j][pos] : letb[j][pos] - letb[i-1][pos];
}

/*
int count_comb(int i, int j, int pos){
	return (i==0) ? cont[j][pos] : cont[j][pos] - cont[i-1][pos];
}
*/

void count(int &res, int &f, int &s){
	res+=f;
	s-=f;
	f=0;
}

int get_distance(int x, int y) {
	for(int i=0;i<3;i++)
		if(count_letter(1,x,y,i)!=count_letter(0,x,y,i)) return -1;

	int ac=(x==0) ? contac[y] : contac[y]-contac[x-1];
	int ca=(x==0) ? contca[y] : contca[y]-contca[x-1];
	int at=(x==0) ? contat[y] : contat[y]-contat[x-1];
	int ta=(x==0) ? contta[y] : contta[y]-contta[x-1];
	int ct=(x==0) ? contct[y] : contct[y]-contct[x-1];
	int tc=(x==0) ? conttc[y] : conttc[y]-conttc[x-1];

	int res=0;	
	(ac<ca) ? count(res,ac,ca) : count(res,ca,ac);
	(at<ta) ? count(res,at,ta) : count(res,ta,at);
	(tc<ct) ? count(res,tc,ct) : count(res,ct,tc);
 
	ac=max(ac,ca);
	at=max(at,ta);
	tc=max(tc,ct);
 
	res+=ac+at;
	
	return res;
}

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