Submission #1155741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155741		curious_tiger	Mutating DNA (IOI21_dna)	C++20	56 / 100	32 ms	5376 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using paira = array<int, 2>;
int n = 1;
vector<int> same(1);
vector<vector<int>> counta(3, vector<int>(1));
auto countb = counta;

void init(string a, string b) {
    n = a.size();
    same.resize(n+1);
    for (int i = 0; i < 3; i++) {
        counta[i].resize(n+1);
        countb[i].resize(n+1);
    }

    for (int i = 0; i < n; i++) {
        int ai = (a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2));
        int bi = (b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2));

        counta[ai][i+1]= (i == 0 ? 1 : counta[(ai)%3][i] + 1);
        counta[(ai + 1)%3][i+1] = (i == 0 ? 0 : counta[(ai + 1)%3][i]);
        counta[(ai + 2) %3][i+1] = (i == 0 ? 0 : counta[(ai + 2)%3][i]);

        countb[bi][i+1]= (i == 0 ? 1 : countb[(bi)%3][i] + 1);
        countb[(bi + 1)%3][i+1] = (i == 0 ? 0 : countb[(bi + 1)%3][i]);
        countb[(bi + 2) %3][i+1] = (i == 0 ? 0 : countb[(bi + 2)%3][i]);

        same[i + 1] = (i == 0 ? 0 : same[i]) + (ai == bi);
    }
}

int get_distance(int x, int y) {

    for (int i = 0; i < 3 ; i++) {
        if (counta[i][y+1] - counta[i][x] != countb[i][y+1] - countb[i][x]) {
            return -1;
        }
    }

    ll ans = 0;
    for (int i = 0; i < 3; i++) {
        ans += counta[i][y+1] - counta[i][x];
    }
    ans -= (same[y+1] - same[x]);
    return (ans + 1)/2;
}

/*
constraints n = 1e5
q = 1e5
at most 3 different
q*log(n) or q solution allowed

same[n] = number of "matching" indices for x and y until n

then

If two strings who are derranged permutations of each other then their edit distance is
for even n n/2
for odd n (n-1)/2 + 1 = (n-1+2)/2 = (n+1)/2

*/

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