Submission #1240978

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240978		gkos5678	Mutating DNA (IOI21_dna)	C++20	0 / 100	21 ms	5792 KiB

dna

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

#define pb push_back
#define X first
#define Y second

const int maxn = 1e5 + 5;

int n;
int pf[3][3][maxn], ar[3][3], kk[2][3];

int f(char c){
    if (c == 'A') return 0;
    if (c == 'C') return 1;
    return 2;
}

void init(string a, string b){
    n = a.size();
    a = '$' + a;
    b = '$' + b;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < 3; j++){
            for (int k = 0; k < 3; k++){
                pf[j][k][i] = pf[j][k][i - 1];
            }
        }

        int c1 = f(a[i]), c2 = f(b[i]);
        pf[c1][c2][i]++;
    }
}

int get_distance(int x, int y){
    x++, y++;
    for (int j = 0; j < 3; j++){
        for (int k = 0; k < 3; k++){
            ar[j][k] = pf[j][k][y] - pf[j][k][x - 1];
            kk[j][0] += ar[j][k];
            kk[k][1] += ar[j][k];
        }
    }
    for (int i = 0; i < 3; i++){
        if (kk[i][0] != kk[i][1]) return -1;
    }

    int ret = 0;
    for (int j = 0; j < 2; j++){
        for (int k = j + 1; k < 3; k++){
            int mn = min(ar[j][k], ar[k][j]);
            ar[j][k] -= mn, ar[k][j] -= mn;
            ret += mn;
        }
    }

    int sm = 0;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            sm += ar[i][j] * (i != j);
    ret += sm * 2 / 3;

    return ret;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:41:22: warning: iteration 2 invokes undefined behavior [-Waggressive-loop-optimizations]
   41 |             kk[k][1] += ar[j][k];
      |             ~~~~~~~~~^~~~~~~~~~~
dna.cpp:38:27: note: within this loop
   38 |         for (int k = 0; k < 3; k++){
      |                         ~~^~~

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