Submission #443301

#	Time	Username	Problem	Language	Result	Execution time	Memory
443301		mario05092929	Mutating DNA (IOI21_dna)	C++17	100 / 100	78 ms	8684 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
string a,b;
int n;
int sumA[3][100005],sumB[3][100005];
int sum[3][3][100005]; // {A,C,T} -> {A,C,T}
int w[300];

void init(string A,string B) {
    a = " "+A, b = " "+B;
    n = a.length()-1;
    w['A'] = 0, w['C'] = 1, w['T'] = 2;
    for(int i = 1;i <= n;i++) {
        for(int j = 0;j < 3;j++) {
            sumA[j][i] += sumA[j][i-1];
            sumB[j][i] += sumB[j][i-1];
            for(int k = 0;k < 3;k++) {
                sum[j][k][i] += sum[j][k][i-1];
            }
        }
        sumA[w[a[i]]][i]++;
        sumB[w[b[i]]][i]++;
        sum[w[a[i]]][w[b[i]]][i]++;
    }
}

int s[3][3];

int Get(int x,int y) {
    return min(s[x][y],s[y][x]);
}

int get_distance(int x, int y) {
    x++, y++;
    for(int i = 0;i < 3;i++) {
        if(sumA[i][y]-sumA[i][x-1] != sumB[i][y]-sumB[i][x-1]) return -1;
    }
    for(int i = 0;i < 3;i++) {
        for(int j = 0;j < 3;j++) {
            s[i][j] = sum[i][j][y]-sum[i][j][x-1];
        }
    }
    int ans = 0,val;
    for(int i = 0;i < 3;i++) {
        val = min(s[i][(i+1)%3],s[(i+1)%3][i]);
        s[i][(i+1)%3] -= val, s[(i+1)%3][i] -= val;
        ans += val;
    }
    return ans+max({s[0][1],s[0][2],s[1][0],s[1][2],s[2][0],s[2][1]})*2;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:22:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   22 |         sumA[w[a[i]]][i]++;
      |                    ^
dna.cpp:23:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |         sumB[w[b[i]]][i]++;
      |                    ^
dna.cpp:24:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         sum[w[a[i]]][w[b[i]]][i]++;
      |                   ^
dna.cpp:24:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |         sum[w[a[i]]][w[b[i]]][i]++;
      |                            ^

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