Submission #790081

#	Time	Username	Problem	Language	Result	Execution time	Memory
790081		alexander707070	Mutating DNA (IOI21_dna)	C++17	100 / 100	33 ms	8592 KiB

dna

#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;

int n,ans;
int pref[MAXN][3],pref2[MAXN][3];
int pairs[MAXN][6];
int a,b,c,d,e,f,curr;

bool ok(int l,int r){
    for(int i=0;i<3;i++){
        if(pref[r][i]-pref[l-1][i] != pref2[r][i]-pref2[l-1][i])return false;
    }
    return true;
}

void init(string a, string b){
    n=int(a.size());

    for(int i=1;i<=n;i++){
        if(a[i-1]=='A')pref[i][0]++;
        if(a[i-1]=='T')pref[i][1]++;
        if(a[i-1]=='C')pref[i][2]++;

        if(b[i-1]=='A')pref2[i][0]++;
        if(b[i-1]=='T')pref2[i][1]++;
        if(b[i-1]=='C')pref2[i][2]++;

        if(a[i-1]=='A' and b[i-1]=='T')pairs[i][0]++;
        if(a[i-1]=='T' and b[i-1]=='A')pairs[i][1]++;

        if(a[i-1]=='A' and b[i-1]=='C')pairs[i][2]++;
        if(a[i-1]=='C' and b[i-1]=='A')pairs[i][3]++;

        if(a[i-1]=='C' and b[i-1]=='T')pairs[i][4]++;
        if(a[i-1]=='T' and b[i-1]=='C')pairs[i][5]++;

        for(int f=0;f<3;f++){
            pref[i][f]+=pref[i-1][f];
            pref2[i][f]+=pref2[i-1][f];
        }

        for(int f=0;f<6;f++){
            pairs[i][f]+=pairs[i-1][f];
        }
    }
}

int get_distance(int x, int y){
    x++; y++;
    if(!ok(x,y))return -1;

    ans=0;

    a=pairs[y][0]-pairs[x-1][0];
    b=pairs[y][1]-pairs[x-1][1];
    c=pairs[y][2]-pairs[x-1][2];
    d=pairs[y][3]-pairs[x-1][3];
    e=pairs[y][4]-pairs[x-1][4];
    f=pairs[y][5]-pairs[x-1][5];

    curr=min(a,b); ans+=curr;
    a-=curr; b-=curr;

    curr=min(c,d); ans+=curr;
    c-=curr; d-=curr;

    curr=min(e,f); ans+=curr;
    e-=curr; f-=curr;

    ans+=2*max(a,b);

    return ans;
}

/*
int main(){
    init("ATACAT", "ACTATA");
    cout<<get_distance(1,3)<<"\n";
    cout<<get_distance(4,5)<<"\n";
    cout<<get_distance(3,5)<<"\n";
}
*/

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