Submission #1155797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155797		an22inkle	Mutating DNA (IOI21_dna)	C++20	100 / 100	44 ms	8960 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));
vector<vector<vector<int>>> ma(3, vector<vector<int>>(3, vector<int>(n)));
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 < 3; i++) {
        for (int j = 0; j < 3; j++) {
            ma[i][j].resize(n+1);
        }
    }

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


        for (int j = 0; j < 3; j++) {
            counta[j][i + 1] = counta[j][i];
            countb[j][ i + 1] = countb[j][i];
        }
        counta[ai][i+1]++;
        countb[bi][i+1]++;

        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                ma[j][k][i+1] = ma[j][k][i];
            }
        }

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

    for (int i = 0; 0 && i < (n + 1); i++) {
        cout << countb[0][i] << ' ';
        cout << countb[1][i] << ' ' ;
        cout << countb[2][i] << '\n';
    }
}

int get_distance(int x, int y) {

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

    int ans = 0;
    for (int i = 0; i < 3; i++) {
        for (int j = i + 1; j < 3; j++) {
            ans += min(ma[i][j][y + 1] - ma[i][j][x], ma[j][i][y + 1] - ma[j][i][x]);
        }
    };
    int a = (ma[0][1][y + 1] - ma[0][1][x]), b= ( ma[1][0][y + 1] - ma[1][0][x]);
    ans += 2*(max(a, b) - min(a ,b));

    return ans; 
}

/*
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: 28 / 28
• Subtask 5: 16 / 16