Submission #1101258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101258		Zero_OP	Mutating DNA (IOI21_dna)	C++17	100 / 100	34 ms	7608 KiB

dna

#include "bits/stdc++.h"

#ifndef LOCAL
    #include "dna.h"
#endif // LOCAL

using namespace std;

int code(char c){
    if(c == 'A') return 0;
    if(c == 'T') return 1;
    if(c == 'C') return 2;
    return -1;
}

const int MAX = 1e5 + 5;

int n, pref[MAX][3][3];

void init(std::string a, std::string b) {
    n = (int)a.size();
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < 3; ++j){
            for(int k = 0; k < 3; ++k){
                pref[i + 1][j][k] = pref[i][j][k];
            }
        }

        ++pref[i + 1][code(a[i])][code(b[i])];
    }
}

int A[3], B[3], cnt[3][3];

int get_distance(int x, int y) {
    ++x; ++y;
    for(int i = 0; i < 3; ++i) {
        A[i] = B[i] = 0;
        for(int j = 0; j < 3; ++j){
            cnt[i][j] = 0;
        }
    }

    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            cnt[i][j] = pref[y][i][j] - pref[x - 1][i][j];
            A[i] += cnt[i][j];
            B[j] += cnt[i][j];
        }
    }

    for(int i = 0; i < 3; ++i){
        if(A[i] != B[i]){
            return -1;
        }
    }

    for(int i = 0; i < 3; ++i){
        cnt[i][i] = 0;
    }

    int ans = 0;

    auto work_greedy = [&](int i, int j){
        int x = min(cnt[i][j], cnt[j][i]);
        ans += x;
        cnt[i][j] -= x;
        cnt[j][i] -= x;
    };

    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            work_greedy(i, j);
        }
    }

    int rest = 0;
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            rest = max(rest, cnt[i][j]);
        }
    }

    ans += rest * 2;

	return ans;
}

#ifdef LOCAL
int main(){
    init("ACT", "ATC");
    cout << get_distance(0, 2) << '\n';
}
#endif // LOCAL

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