Submission #479214

#	Time	Username	Problem	Language	Result	Execution time	Memory
479214		couplefire	Mutating DNA (IOI21_dna)	C++17	100 / 100	55 ms	7412 KiB

dna

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

const int N = 100005;

int n, cnt[3][3][N];

void init(string a, string b){
    n = a.size();
    for(auto &c : a)
        if(c=='A') c = '0';
        else if(c=='C') c = '1';
        else c = '2';
    for(auto &c : b)
        if(c=='A') c = '0';
        else if(c=='C') c = '1';
        else c = '2';
    a = "$"+a, b = "$"+b;
    for(int i = 0; i<3; ++i)
        for(int j = 0; j<3; ++j)
            for(int id = 1; id<=n; ++id)
                cnt[i][j][id] = cnt[i][j][id-1]+(a[id]-'0'==i && b[id]-'0'==j);
}

int get_distance(int l, int r){
    ++l, ++r; int ans = 0;
    int tmp[3][3]; memset(tmp, 0, sizeof tmp);
    for(int i = 0; i<3; ++i)
        for(int j = 0; j<3; ++j)
            tmp[i][j] = cnt[i][j][r]-cnt[i][j][l-1];
    for(int i = 0; i<3; ++i)
        for(int j = i+1; j<3; ++j){
            int x = min(tmp[i][j], tmp[j][i]);
            ans += x, tmp[i][j] -= x, tmp[j][i] -= x;
        }
    if(tmp[0][1] != tmp[1][2] || tmp[0][1] != tmp[2][0] || 
       tmp[1][0] != tmp[2][1] || tmp[1][0] != tmp[0][2]) return -1;
    ans += 2*(tmp[0][1]+tmp[1][0]);
    return ans;
}

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