Submission #441303

#	Time	Username	Problem	Language	Result	Execution time	Memory
441303		pere_gil	Mutating DNA (IOI21_dna)	C++17	0 / 100	56 ms	7876 KiB

dna

#include "bits/stdc++.h"
#include "dna.h"
using namespace std;

string a,b;
// ac ca at ta ct tc
vector<vector<int> > cont;

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;
}

void init(std::string A, std::string B) {
	a=A;
	b=B;
	int n=a.size();
	cont.resize(n,vector<int> (6,0));
	
	cont[0][get_comb(a[0],b[0])]++;
	for(int i=1;i<n;i++){
		for(int j=0;j<6;j++)
			cont[i][j]=cont[i-1][j];
		cont[i][get_comb(a[i],b[i])]++;
	}
}

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) {
	vector<int> v(6);
	for(int i=0;i<6;i++)
		v[i]=count_comb(x,y,i);
	
	int res=0;
	for(int i=0;i<6;i+=2)
		(v[i]<v[i+1]) ? count(res,v[i],v[i+1]) : count(res,v[i+1],v[i]);
	vector<int> aux(3);
	for(int i=0;i<3;i++)
		aux[i]=max(v[2*i],v[2*i+1]);
	if(aux[0]!=aux[1] || aux[1]!=aux[2] || aux[0]!=aux[2]) return -1;
	res+=aux[0]+aux[1];
	return res;
}

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