Submission #866116

#	Time	Username	Problem	Language	Result	Execution time	Memory
866116		Bula	Mutating DNA (IOI21_dna)	C++17	100 / 100	95 ms	23900 KiB

dna

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

const int N = 1e5 + 5;
int pref[N][5][5], cnt[N][5][5];

void init(string s, string t){
    int n = s.size();
    s = '.' + s;
    t = '.' + t;
    vector<int> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; i++){
        if(s[i] == 'A'){
            a[i] = 1;
        }
        else if(s[i] == 'C'){
            a[i] = 2;
        }else a[i] = 3;

        if(t[i] == 'A'){
            b[i] = 1;
        }
        else if(t[i] == 'C'){
            b[i] = 2;
        }else b[i] = 3;
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 3; j++){
            for(int k = 1; k <= 3; k++){
                pref[i][j][k] = pref[i - 1][j][k];
                cnt[i][j][k] = cnt[i - 1][j][k];
            }
        }
        cnt[i][a[i]][1]++;
        cnt[i][b[i]][2]++;
        pref[i][a[i]][b[i]]++;
    }
}


int get_distance(int l, int r){
    l++;r++;
    for(int i = 1; i <= 3; i++){
        int a = cnt[r][i][1] - cnt[l - 1][i][1];
        int b = cnt[r][i][2] - cnt[l - 1][i][2];
        if(a != b) return -1;
    }
    int ans = 0;
    map< pair<int, int>, int> mp;
    for(int i = 1; i <= 3; i++){
        for(int j = 1; j <= 3; j++){
            int a = pref[r][i][j] - pref[l - 1][i][j];
            mp[{i, j}] = a;
        }
    }
    for(int i = 1; i <= 3; i++){
        for(int j = i + 1; j <= 3; j++){
            int mn = min(mp[{i, j}], mp[{j, i}]);
            ans += mn;
            mp[{i, j}] -= mn;
            mp[{j, i}] -= mn;
        }
    }
    int cnt = 0;
    for(int i = 1; i <= 3; i++){
        for(int j = 1; j <= 3; j++){
            if(i == j) continue;
            cnt += mp[{i, j}];
        }
    }
    ans += (2 * cnt) / 3;
    return ans;
}

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