Submission #1014853

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014853		aufan	Mutating DNA (IOI21_dna)	C++17	100 / 100	37 ms	8256 KiB

dna

// #include "dna.h"
#include <bits/stdc++.h>

using namespace std;
int n;
vector<vector<int>> pref(6, vector<int>(111111));
vector<vector<int>> pref2(3, vector<int>(111111));
void init(string a, string b) {
    map<string, int> cd;
    cd["AT"] = 0;
    cd["TC"] = 1;
    cd["CA"] = 2;
    cd["AC"] = 3;
    cd["CT"] = 4;
    cd["TA"] = 5;
    n = a.size();
    a = '?' + a;
    b = '?' + b;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < 6; j++) {
            pref[j][i] = pref[j][i-1];
        }
        for (int j = 0; j < 3; j++) {
            pref2[j][i] = pref2[j][i-1];
        }
        pref2[(a[i] == 'A' ? 0 : a[i] == 'T' ? 1 : 2)][i]++;
        pref2[(b[i] == 'A' ? 0 : b[i] == 'T' ? 1 : 2)][i]--;
        if (a[i] == b[i]) continue;
        string x = "";
        x.push_back(a[i]);
        x.push_back(b[i]);
        pref[cd[x]][i]++;
    }
}

int get_distance(int x, int y) {
    ++x;
    ++y;
    vector<int> ct(6);
    for (int j = 0; j < 6; j++) {
        ct[j] = pref[j][y] - pref[j][x-1];
    }
    for (int j = 0; j < 3; j++) {
        if (pref2[j][y] - pref2[j][x-1] != 0) {
            return -1;
        }
    }
    int ans = 0;
    for (int j = 0; j < 3; j++) {
        int z = min(ct[j], ct[5-j]);
        ct[j] -= z;
        ct[5-j] -= z;
        ans += z;
    }
    ans += 2*(ct[0] + ct[3]);
    return ans;
}

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