Submission #1216851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216851		islam_2010	Mutating DNA (IOI21_dna)	C++20	35 / 100	19 ms	3916 KiB

dna

#pragma GCC optimize("O3")
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

string s, c;
const int sz = 100005;
int pref_diff[sz], pref_A_s[sz], pref_A_c[sz];

void init(string a, string b){
    s = a;
    c = b;
    int n = s.size();
    pref_diff[0] = (s[0] != c[0]);
    pref_A_s[0] = (s[0] == 'A');
    pref_A_c[0] = (c[0] == 'A');

    for (int i = 1; i < n; ++i) {
        pref_diff[i] = pref_diff[i-1] + (s[i] != c[i]);
        pref_A_s[i] = pref_A_s[i-1] + (s[i] == 'A');
        pref_A_c[i] = pref_A_c[i-1] + (c[i] == 'A');
    }
}

int get_distance(int x, int y){
    int a1 = pref_A_s[y] - (x > 0 ? pref_A_s[x-1] : 0);
    int a2 = pref_A_c[y] - (x > 0 ? pref_A_c[x-1] : 0);

    if (a1 != a2) return -1;

    bool match = true;
    for (int i = x; i <= y; ++i) {
        if (s[i] != c[i]) {
            match = false;
            break;
        }
    }
    if (match) return 0;

    int mismatch = pref_diff[y] - (x > 0 ? pref_diff[x-1] : 0);

    return (mismatch + 1) / 2;
}

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