Submission #1195946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195946		edga1	Mutating DNA (IOI21_dna)	C++20	100 / 100	23 ms	8456 KiB

dna

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define pb push_back
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define MOD 1000000007
int sk[100005][3][3];
int ska[100005][3], skb[100005][3];

void init(string a, string b){
    for(int i=1; i<=a.size(); i++){
        for(int j=0; j<3; j++){
            ska[i][j]=ska[i-1][j];
            skb[i][j]=skb[i-1][j];
            for(int z=0; z<3; z++){
                sk[i][j][z]=sk[i-1][j][z];
            }
        }
        int ac,bc;
        if(a[i-1]=='A') ac=0;
        if(a[i-1]=='T') ac=1;
        if(a[i-1]=='C') ac=2;
        if(b[i-1]=='A') bc=0;
        if(b[i-1]=='T') bc=1;
        if(b[i-1]=='C') bc=2;
        ska[i][ac]++;
        skb[i][bc]++;
        sk[i][ac][bc]++;
    }
}

int get_distance(int x, int y){
    x++;
    y++;
    for(int i=0; i<3; i++){
        if(ska[y][i]-ska[x-1][i]!=skb[y][i]-skb[x-1][i]) return -1;
    }
    int n=y-x+1;
    int g=0,d=0;
    for(int i=0; i<3; i++){
        g+=sk[y][i][i]-sk[x-1][i][i];
    }
    d+=min(sk[y][0][1]-sk[x-1][0][1],sk[y][1][0]-sk[x-1][1][0]);
    d+=min(sk[y][1][2]-sk[x-1][1][2],sk[y][2][1]-sk[x-1][2][1]);
    d+=min(sk[y][0][2]-sk[x-1][0][2],sk[y][2][0]-sk[x-1][2][0]);
    g+=d*2;
    d+=(n-g)/3*2;
    return d;
}

/*int main(){
    string a,b;
    cin>>a>>b;
    init(a,b);
    int q; cin>>q;
    for(int i=0; i<q; i++){
        int x,y;
        cin>>x>>y;
        cout<<get_distance(x,y)<<'\n';
    }
    return 0;
}*/

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