Submission #1191674

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191674		Petrix	Mutating DNA (IOI21_dna)	C++20	43 / 100	21 ms	3908 KiB

dna

#include <iostream>
#include <string>
#include <map>
#include "dna.h"
using namespace std;

string v1,v2;
map<pair<int,int>,int> frvv;
int spa[100001];
int spb[100001];
int spd[100001];
void init(string a,string b){
    v1=a;v2=b;int i;
    for(i=0;i<a.size();i++){
        if(i){
            spa[i]=spa[i-1];spb[i]=spb[i-1];spd[i]=spd[i-1];
        }
        if(a[i]=='A') spa[i]++;
        if(b[i]=='A') spb[i]++;
        if(a[i]!=b[i]) spd[i]++;
    }
}


int get_distance(int x,int y){
    if(y-x<=1e3){
        int cnt=0,i,auxcnt=0;int frv[3]={0,0,0},frv1[3]={0,0,0};
        frvv.clear();

        for(i=x;i<=y;i++){
            if(v1[i]=='T') frv[0]++;
            if(v2[i]=='T') frv1[0]++;

            if(v1[i]=='A') frv[1]++;
            if(v2[i]=='A') frv1[1]++;

            if(v1[i]=='C') frv[2]++;
            if(v2[i]=='C') frv1[2]++;
        }
        if(frv[0]!=frv1[0] || frv[1]!=frv1[1] || frv[2]!=frv1[2]) return -1;
        for(i=x;i<=y;i++){
            if(v1[i]!=v2[i] && !frvv[{v2[i],v1[i]}]){
                cnt++;frvv[{v1[i],v2[i]}]++;
            }else if(v1[i]!=v2[i]){
                cnt--;frvv[{v2[i],v1[i]}]--;auxcnt++;
            }
        }
        return max(cnt-1,0)+auxcnt;
    }else{
        if((x==0 && spa[y]!=spb[y]) && (x!=0 && spa[y]-spa[x-1]!=spb[y]-spb[x-1])) return -1;
        if(!x){
            return spd[y]/2;
        }else return (spd[y]-spd[x-1])/2;
    }

}

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