Submission #583665

#	Time	Username	Problem	Language	Result	Execution time	Memory
583665		Cauchico	Mutating DNA (IOI21_dna)	C++17	100 / 100	50 ms	6152 KiB

dna

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

int n;
vector<array<int,6>> arr; //ac,at,ca,ct,ta,tc
void init(string a, string b) {
    n = a.size();
    arr.resize(n+1);
    for (int i=0;i<n;i++) {
        arr[i+1] = arr[i];
        if (a[i] == 'A') {
            if (b[i] == 'C') {
                arr[i+1][0]++;
            }
            if (b[i] == 'T') {
                arr[i+1][1]++;
            }
        }
        if (a[i] == 'C') {
            if (b[i] == 'A') {
                arr[i+1][2]++;
            }
            if (b[i] == 'T') {
                arr[i+1][3]++;
            }
        }
        if (a[i] == 'T') {
            if (b[i] == 'A') {
                arr[i+1][4]++;
            }
            if (b[i] == 'C') {
                arr[i+1][5]++;
            }
        }
    }
}

int get_distance(int x, int y) {
    y++;
    int aa = arr[y][0] + arr[y][1] - arr[x][0] - arr[x][1];
    int ab = arr[y][2] + arr[y][4] - arr[x][2] - arr[x][4];
    int ca = arr[y][2] + arr[y][3] - arr[x][2] - arr[x][3];
    int cb = arr[y][0] + arr[y][5] - arr[x][0] - arr[x][5];
    int ta = arr[y][4] + arr[y][5] - arr[x][4] - arr[x][5];
    int tb = arr[y][1] + arr[y][3] - arr[x][1] - arr[x][3];
    if (aa-ab != 0 or ca-cb != 0 or ta-tb != 0) {
        return -1;
    }
    array<int,6> diff;
    for (int i=0;i<6;i++) {
        diff[i] = arr[y][i] - arr[x][i];
    }
    int ans = min(diff[0],diff[2])+min(diff[1],diff[4])+min(diff[3],diff[5]);
    int uni = abs(diff[0]-diff[2])+abs(diff[1]-diff[4])+abs(diff[3]-diff[5]);
    
    return ans + 2*uni/3;
}

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