Submission #1244441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244441		vtnoo	Mutating DNA (IOI21_dna)	C++20	100 / 100	27 ms	8456 KiB

dna

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN=100005;
int N;
int p[MAXN][3][3];
pair<int,int> a[MAXN], t[MAXN], c[MAXN];

void init(string x, string y){
    N=x.size();
    auto id=[&](char &c){
        if(c=='A')return 0;
        else if(c=='T')return 1;
        else return 2;
    };
    for(int i=0;i<N;i++){
        if(x[i]=='A'){
            a[i+1].first++;
        }else if(x[i]=='T'){
            t[i+1].first++;
        }else{
            c[i+1].first++;
        }
        if(y[i]=='A'){
            a[i+1].second++;
        }else if(y[i]=='T'){
            t[i+1].second++;
        }else{
            c[i+1].second++;
        }
    }
    for(auto &d:{a, t, c}){
        for(int i=1;i<=N;i++){
            d[i].first+=d[i-1].first;
            d[i].second+=d[i-1].second;
        }
    }
    for(int i=0;i<N;i++){
        int pa=id(x[i]);
        int pb=id(y[i]);
        if(pa==pb)continue;
        p[i+1][pa][pb]++;
    }
    for(int i=1;i<=N;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++){
                p[i][j][k]+=p[i-1][j][k];
            }
        }
    }
}

int get_distance(int x, int y){
    x++;y++;
    int cnt_a=a[y].first-a[x-1].first;
    int cnt_a2=a[y].second-a[x-1].second;
    int cnt_t=t[y].first-t[x-1].first;
    int cnt_t2=t[y].second-t[x-1].second;
    int cnt_c=c[y].first-c[x-1].first;
    int cnt_c2=c[y].second-c[x-1].second;
    if(cnt_a!=cnt_a2||cnt_t!=cnt_t2||cnt_c!=cnt_c2){
        return -1;
    }      
    int c[3][3];
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            c[i][j]=p[y][i][j]-p[x-1][i][j];
        }
    }
    int d=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            int r;
            r=min(c[i][j], c[j][i]);
            c[i][j]-=r;
            c[j][i]-=r;
            d+=r;
        }
    }
    int s=0;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            if(c[i][j]){
                s+=c[i][j];
            }
        }
    }
    return d+(s/3)*2;
}

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