Submission #998830

#	Time	Username	Problem	Language	Result	Execution time	Memory
998830		fryingduc	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	8888 KiB

dna

#include "bits/stdc++.h"
//#include "dna.h"
using namespace std;

int n;
const int maxn = 1e5 + 5;
int pref_a[maxn][3];
int pref_b[maxn][3];
int same[maxn];
int f[maxn][3][3];

void init(string a, string b) {
    n = a.size();
    a = ' ' + a;
    b = ' ' + b;
    
    for(int i = 1; i <= n; ++i) {
        if(a[i] == 'T') a[i] = 'B';
        if(b[i] == 'T') b[i] = 'B';
    }
    
    for(int i = 1; i <= n; ++i) {
        same[i] = same[i - 1] + (a[i] == b[i]);
        for(int j = 0; j < 3; ++j) {
            pref_a[i][j] = pref_a[i - 1][j];
            pref_b[i][j] = pref_b[i - 1][j];
        }
        pref_a[i][a[i] - 'A']++;
        pref_b[i][b[i] - 'A']++;
    }
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j < 3; ++j) {
            for(int k = 0; k < 3; ++k) {
                f[i][j][k] = f[i - 1][j][k];
            }
        }
        f[i][a[i] - 'A'][b[i] - 'A']++;
    }
}
int get_distance(int x, int y) {
    ++x, ++y;
    int res = 0;
    for(int i = 0; i < 3; ++i) {
        if(pref_a[y][i] - pref_a[x - 1][i] != pref_b[y][i] - pref_b[x - 1][i]) {
            return -1;
        }
    }
    int rem = 0;
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < i; ++j) {
            res += abs(f[y][i][j] - f[x - 1][i][j] - f[y][j][i] + f[x - 1][j][i]);
            rem += min(f[y][i][j] - f[x - 1][i][j], f[y][j][i] - f[x - 1][j][i]);
        }
    }
    return rem + res / 3 * 2;    
}

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