Submission #835188

#	Time	Username	Problem	Language	Result	Execution time	Memory
835188		Mohmad_Zaid	Mutating DNA (IOI21_dna)	C++17	100 / 100	31 ms	6528 KiB

dna

// #include "dna.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>one_two,two_one,two_three,three_two,one_three,three_one;
void init(string a, string b) {
    int n=a.size();
    vector<int>arr1(a.size(),0),arr2(b.size(),0);
    one_two.resize(n+1,0);
    two_one.resize(n+1,0);
    two_three.resize(n+1,0);
    three_two.resize(n+1,0);
    one_three.resize(n+1,0);
    three_one.resize(n+1,0);
    for(int i=0;i<n;i++){
        arr1[i]+=1*(a[i]=='A');
        arr1[i]+=2*(a[i]=='T');
        arr1[i]+=3*(a[i]=='C');
        arr2[i]+=1*(b[i]=='A');
        arr2[i]+=2*(b[i]=='T');
        arr2[i]+=3*(b[i]=='C');
    }
    // for(int i=0;i<n;i++)cout<<arr1[i]<<' ';cout<<endl;
    // for(int i=0;i<n;i++)cout<<arr2[i]<<' ';cout<<endl;
    for(int i=0;i<n;i++){
        int v=arr1[i]+arr2[i];
        if(a[i]!=b[i]){
            if(v==3){
                if(arr1[i]==1)one_two[i+1]=1;
                else two_one[i+1]=1;
            }else if(v==5){
                if(arr1[i]==2)two_three[i+1]=1;
                else three_two[i+1]=1;
            }else{
                if(arr1[i]==1)one_three[i+1]=1;
                else three_one[i+1]=1;
            }
        }
        one_two[i+1]+=one_two[i];
        two_one[i+1]+=two_one[i];
        two_three[i+1]+=two_three[i];
        three_two[i+1]+=three_two[i];
        one_three[i+1]+=one_three[i];
        three_one[i+1]+=three_one[i];
    }
    // for(int i=1;i<=n;i++)cout<<one_two[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<two_one[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<two_three[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<three_two[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<one_three[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<three_one[i]<<' ';cout<<endl;
}

int get_distance(int x, int y) {
    int sm=0;
    int o_t=one_two[y+1]-one_two[x];
    int t_o=two_one[y+1]-two_one[x];
    int t_c=two_three[y+1]-two_three[x];
    int c_t=three_two[y+1]-three_two[x];
    int o_c=one_three[y+1]-one_three[x];
    int c_o=three_one[y+1]-three_one[x];
    // cout<<o_t<<' '<<t_o<<endl;
    // cout<<t_c<<' '<<c_t<<endl;
    // cout<<o_c<<' '<<c_o<<endl;
    if((o_t+o_c)!=(c_o+t_o)){return -1;}
    if((t_o+t_c)!=(o_t+c_t)){return -1;}
    if((c_o+c_t)!=(o_c+t_c)){return -1;}
    int mn=min(o_t,t_o);
    int mn2=min(t_c,c_t);
    int mn3=min(o_c,c_o);
    // cout<<mn<<' '<<mn2<<' '<<mn3<<endl;
    o_t-=mn;t_o-=mn;
    t_c-=mn2;c_t-=mn2;
    o_c-=mn3;c_o-=mn3;
    // cout<<o_t<<' '<<t_o<<endl;
    // cout<<t_c<<' '<<c_t<<endl;
    // cout<<o_c<<' '<<c_o<<endl;
    sm+=(mn+mn2+mn3);
    sm+=(o_t+t_o+t_c+c_t+o_c+c_o)/3*2;
	return sm;
}

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