Submission #530325

#	Time	Username	Problem	Language	Result	Execution time	Memory
530325		gg123_pe	Mutating DNA (IOI21_dna)	C++17	100 / 100	43 ms	6468 KiB

dna

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

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1e5 + 5; 

int n, su[N][6]; 
string s, t; 

void init(string a, string b){
    s = a, t = b, n = a.size();
    f(i,1,n+1){
        f(j,0,6) su[i][j] = su[i-1][j];
        if(s[i-1] == 'A' and t[i-1] == 'C') su[i][0]++; 
        if(s[i-1] == 'A' and t[i-1] == 'T') su[i][1]++; 
        if(s[i-1] == 'C' and t[i-1] == 'A') su[i][2]++; 
        if(s[i-1] == 'C' and t[i-1] == 'T') su[i][3]++; 
        if(s[i-1] == 'T' and t[i-1] == 'A') su[i][4]++;
        if(s[i-1] == 'T' and t[i-1] == 'C') su[i][5]++; 
    }
}
int get_distance(int x, int y){
    x++, y++; 
    int ac, at, ca, ct, ta, tc; 
    ac =su[y][0]-su[x-1][0]; at =su[y][1]-su[x-1][1]; ca =su[y][2]-su[x-1][2];
    ct =su[y][3]-su[x-1][3]; ta =su[y][4]-su[x-1][4]; tc =su[y][5]-su[x-1][5];

    if(ac + at != ca + ta or ct + ca != ac + tc or ta + tc != ct + at) return -1; 
    int add = max(ac, ca) - min(ac, ca), ans;
    ans = min(ac, ca) + min(at, ta) + min(ct, tc); 
    return ans + add*2; 
}

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