Submission #1197351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197351		AMel0n	Mutating DNA (IOI21_dna)	C++20	100 / 100	36 ms	8008 KiB

dna

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

typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first 
#define S seconds

int n;
vector<vector<int>> ps;
void init(string a, string b) {
    n = a.size();
    ps.resize(n+1, vector<int>(6));
    for(int i = 1; i <= n; i++) {
        for(int k = 0; k < 6; k++) ps[i][k] = ps[i-1][k];

        if (a[i-1] == 'A' && b[i-1] == 'C') ps[i][0]++;
        if (a[i-1] == 'C' && b[i-1] == 'A') ps[i][1]++;
        if (a[i-1] == 'A' && b[i-1] == 'T') ps[i][2]++;
        if (a[i-1] == 'T' && b[i-1] == 'A') ps[i][3]++;
        if (a[i-1] == 'C' && b[i-1] == 'T') ps[i][4]++;
        if (a[i-1] == 'T' && b[i-1] == 'C') ps[i][5]++;
    }
}


int get_distance(int x, int y) {
    vector<int> range;
    for(int k = 0; k < 6; k++) range.push_back(ps[y+1][k] - ps[x][k]);

    int sigma = min(range[0], range[1]) + min(range[2], range[3]) + min(range[4], range[5]); 
    int skibidi = max(range[0], range[1]) - min(range[0], range[1]) + max(range[2], range[3]) - min(range[2], range[3]) + max(range[4], range[5]) - min(range[4], range[5]);

    if (range[0] + range[2] != range[1] + range[3] || range[1] + range[4] != range[0] + range[5] || range[3] + range[5] != range[2] + range[4]) return -1; 

    return sigma + (skibidi * 2) / 3;
}

// signed main() {
//     cin.tie(0); ios::sync_with_stdio(false);
// }

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