Submission #1282932

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282932		baotoan655	Mutating DNA (IOI21_dna)	C++20	100 / 100	32 ms	8340 KiB

dna

#include <bits/stdc++.h>
#define file(name)  if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
using namespace std;

const int N = 1e5 + 5;
int pref[3][3][N];
int s1[3][N];
int s2[3][N];
map<char, int> f;

void init(string a, string b) {
    f['A'] = 0;
    f['C'] = 1;
    f['T'] = 2;
    int n = (int) a.size();
    a = ' ' + a;
    b = ' ' + b;
    for (int i = 1; i <= n; i++) {
        for (int k = 0; k < 3; k++) {
            for (int l = 0; l < 3; l++) {
                pref[k][l][i] = pref[k][l][i - 1] + (f[a[i]] == k && f[b[i]] == l);
            }
            s1[k][i] = s1[k][i - 1] + (f[a[i]] == k);
            s2[k][i] = s2[k][i - 1] + (f[b[i]] == k);
        }
    }
}
int get_distance(int x, int y) {
    x++;
    y++;
    for (int t = 0; t < 3; t++) {
        if (s1[t][y] - s1[t][x - 1] != s2[t][y] - s2[t][x - 1]) {
            return -1;
        }
    }
    int ans = 0, kk = 0;
    for (int k = 0; k < 3; k++) {
        for (int l = k + 1; l < 3; l++) {
            ans += min(pref[k][l][y] - pref[k][l][x - 1], pref[l][k][y] - pref[l][k][x - 1]);
            if (k == 0 and l == 1) kk = abs((pref[k][l][y] - pref[k][l][x - 1]) - (pref[l][k][y] - pref[l][k][x - 1]));
        }
    }
    return ans + 2 * kk;
}

//int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(0), cout.tie(0);
//
////    file("A") else file("task");
//
//    return 0;
//}

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