Submission #529025

#	Time	Username	Problem	Language	Result	Execution time	Memory
529025		happypotato	Mutating DNA (IOI21_dna)	C++17	100 / 100	47 ms	7408 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e5 + 1;
int ps[mxN][9];
map<char, int> conv = {{'A', 0}, {'C', 1}, {'T', 2}};
void init(string a, string b) {
    int n = a.length();
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 9; j++) {
            ps[i][j] = ps[i - 1][j];
            ps[i][j] = ps[i - 1][j];
        }
        ps[i][conv[a[i - 1]] * 3 + conv[b[i - 1]]]++;
    }
}
int get_distance(int x, int y) {
    x++; y++;
    int freq[9];
    for (int i = 0; i < 9; i++) freq[i] = ps[y][i] - ps[x - 1][i];
    int ans = 0;
    int cur;
    freq[0] = freq[4] = freq[8] = 0;
    cur = min(freq[1], freq[3]); ans += cur; freq[1] -= cur; freq[3] -= cur; // 01
    cur = min(freq[2], freq[6]); ans += cur; freq[2] -= cur; freq[6] -= cur; // 02
    cur = min(freq[5], freq[7]); ans += cur; freq[5] -= cur; freq[7] -= cur; // 12
    cur = min({freq[1], freq[5], freq[6]}); ans += cur * 2; freq[1] -= cur; freq[5] -= cur; freq[6] -= cur; // 012
    cur = min({freq[2], freq[7], freq[3]}); ans += cur * 2; freq[2] -= cur; freq[7] -= cur; freq[3] -= cur; // 021
    for (int i = 0; i < 9; i++) {
        if (freq[i]) return -1;
    }
    return ans;
}

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