제출 #438867

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438867		victoriad	DNA 돌연변이 (IOI21_dna)	C++17	84 / 100	1573 ms	6312 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;
	int n=aa.size();
	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 if(ac[n-1]==0 && bc[n-1]==0){
		int h=mismo[y+1]-mismo[x];
		int lon=y-x;
		return (lon-h+1)/2;
	}

	else{
		int l=y-x;
		vector<bool>co(l,false);
		int sp=0;
		int p=0;
		for(int i=x;i<y;i++){
			if(g[i]==j[i])co[i-x]=true;
		}
		for(int i=x;i<y;i++){
			if(!co[i-x]){
				for(int k=i+1;k<y;k++){
					if(g[i]==j[k] && g[k]==j[i] && !co[k-x]){
						p++;
						co[i-x]=true;
						co[k-x]=true;
						break;
					}
				}
				if(!co[i-x])sp++;
			}
		}
		p+=(sp/3)*2;
		p+=sp%3;
		return p;
	}
	}
	if(!pos)return -1;
	return 0;
}

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