Submission #1217895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217895		hengliao	Mutating DNA (IOI21_dna)	C++20	100 / 100	28 ms	12048 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=1e5+5;

    ll n;
    ll pre[mxN][6];
    ll val[mxN][6];
    ll pre2[mxN][3];
    ll val2[mxN][3];
}

void init(string a, string b) {
    n=a.length();
    memset(pre, 0, sizeof(pre));
    memset(val, 0, sizeof(val));
    for(ll i=0;i<n;i++){
        if(a[i]==b[i]) continue;
        if(a[i]=='T' && b[i]=='A'){
            val[i][0]++;
        }
        else if(a[i]=='A' && b[i]=='T'){
            val[i][1]++;
        }
        else if(a[i]=='T' && b[i]=='C'){
            val[i][2]++;
        }
        else if(a[i]=='C' && b[i]=='T'){
            val[i][3]++;
        }
        else if(a[i]=='C' && b[i]=='A'){
            val[i][4]++;
        }
        else if(a[i]=='A' && b[i]=='C'){
            val[i][5]++;
        }
    }

    for(ll i=0;i<n;i++){
        for(ll j=0;j<6;j++){
            pre[i+1][j]=pre[i][j]+val[i][j];
        }
    }
}

int get_distance(int x, int y) {
	ll tep[6]={};
    for(ll i=0;i<6;i++){
        tep[i]=pre[y+1][i]-pre[x][i];
    }
    if((tep[1]+tep[5])!=(tep[0]+tep[4])){
        return -1;
    }
    if((tep[0]+tep[2])!=(tep[1]+tep[3])){
        return -1;
    }
    if((tep[3]+tep[4])!=(tep[2]+tep[5])){
        return -1;
    }
    ll ans=0;
    for(ll i=0;i<6;i+=2){
        ans+=min(tep[i], tep[i+1]);
    }
    ans+=2*(max(tep[0], tep[1])-min(tep[0], tep[1]));
    return (int) ans;
}

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