Submission #1241379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241379		Younis_Dwai	Mutating DNA (IOI21_dna)	C++20	100 / 100	27 ms	12812 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
#define in insert
#define pb push_back
using namespace std;
const int N=1e5+5;
int n,B[N],C[N],pref[2][N][4],d[N][2],cnt[N][4][4];
void init(std::string a, std::string b){
     n=a.size();
     for(int i=1;i<=n;i++){
            if(a[i-1]=='A') B[i]=1;
            else if(a[i-1]=='T') B[i]=2;
            else B[i]=3;
     }
     for(int i=1;i<=n;i++){
            if(b[i-1]=='A') C[i]=1;
            else if(b[i-1]=='T') C[i]=2;
            else C[i]=3;
     }
     for(int i=1;i<=n;i++){
         for(int j=1;j<=3;j++){
             pref[0][i][j]=pref[0][i-1][j]+bool(B[i]==j);
             pref[1][i][j]=pref[1][i-1][j]+bool(C[i]==j);
             for(int k=1;k<=3;k++){
                 cnt[i][j][k]=cnt[i-1][j][k]+bool(B[i]==j && C[i]==k);
             }
         }
     }
     return ;
}

int get_distance(int x, int y){
    ++x;++y;
    bool can=1;
    for(int j=1;j<=3;j++){
        if(pref[0][y][j]-pref[0][x-1][j]!=pref[1][y][j]-pref[1][x-1][j]) can=0;
    }
    if(!can) return -1;
    int ret=0;
    int cur[4][4];
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            cur[i][j]=cnt[y][i][j]-cnt[x-1][i][j];
        }
    }
    for(int i=1;i<=3;i++){
        for(int j=i+1;j<=3;j++){
            int most=min(cur[i][j],cur[j][i]);
            cur[i][j]-=most;
            cur[j][i]-=most;
            ret+=most;
        }
    }
    int sum=0;
    for(int i=1;i<=3;i++){
        for(int j=1;j<=3;j++){
            if(i==j) continue ;
            sum+=cur[i][j];
        }
    }
    ret+=(sum/3)*2;
	return ret;
}

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