Submission #438861

#	Time	Username	Problem	Language	Result	Execution time	Memory
438861		victoriad	Mutating DNA (IOI21_dna)	C++17	56 / 100	52 ms	5564 KiB

dna

#include <cmath>
#include <iostream>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
#include <fstream>
#include "dna.h"

using namespace std;
vector<int>aa;
vector<int>ab;
vector<int>ac;
vector<int>ba;
vector<int>bb;
vector<int>bc;
vector<int>mismo;
string j;
string g;
void init(std::string a, std::string b) {
	j=a;
	g=b;
	int n=a.size();
	aa.assign(n+1,0);
	ab.assign(n+1,0);
	ac.assign(n+1,0);
	ba.assign(n+1,0);
	bb.assign(n+1,0);
	bc.assign(n+1,0);
	mismo.assign(n+1,0);
	for(int i=1;i<=n;i++){
		mismo[i]=mismo[i-1];
		if(a[i-1]==b[i-1]){
			mismo[i]=mismo[i-1]+1;
		}
	}
	for(int i=1;i<n+1;i++){
        aa[i]=aa[i-1];
        ab[i]=ab[i-1];
        ac[i]=ac[i-1];
        ba[i]=ba[i-1];
        bb[i]=bb[i-1];
        bc[i]=bc[i-1];
		if(a[i-1]=='A')aa[i]=aa[i-1]+1;
		else if(a[i-1]=='T')ab[i]=ab[i-1]+1;
		else if(a[i-1]=='C')ac[i]=ac[i-1]+1;
		if(b[i-1]=='A')ba[i]=ba[i-1]+1;
		else if(b[i-1]=='T')bb[i]=bb[i-1]+1;
		else if(b[i-1]=='C')bc[i]=bc[i-1]+1;
	}
}

int get_distance(int x, int y) {
	bool pos=true;
	if(aa[y+1]-aa[x]!=ba[y+1]-ba[x])pos=false;
	else if(ab[y+1]-ab[x]!=bb[y+1]-bb[x])pos=false;
	else if (ac[y+1]-ac[x]!=bc[y+1]-bc[x])pos=false;
	if(pos){
	if(x==y)return 0;
	if(y-x==1){
		if(j[x]!=g[x])return 1;
		else return 0;
	}
	else if(y-x==2){
		int h=mismo[y+1]-mismo[x];
		if(h==3)return 0;
		else if(h==2 ||h==1)return 1;
		else return 2;
	}
	else{
		int h=mismo[y+1]-mismo[x];
		int lon=y-x;
		if((lon-h)%2)
		return (lon-h+1)/2;
		else{
			return (lon-h+1)/2 +1;
		}
	}
	}
	if(!pos)return -1;
	return 0;
}

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