Submission #569522

#	Time	Username	Problem	Language	Result	Execution time	Memory
569522		PiejanVDC	Mutating DNA (IOI21_dna)	C++17	100 / 100	98 ms	20368 KiB

dna

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

vector<vector<int>>v;
vector<vector<int>>cntA,cntB;

int T(char a, char b) {
    if(a == 'A' && b == 'T')
        return 0;
    if(a == 'T' && b == 'A')
        return 1;
    if(a == 'C' && b == 'T')
        return 2;
    if(a == 'T' && b == 'C')
        return 3;
    if(a == 'C' && b == 'A')
        return 4;
    if(a == 'A' && b == 'C')
        return 5;
    return 100;
}

void init(string a, string b) {
    const int n = (int)a.length();
    v.resize(n+1, vector<int>(6,0));
    cntA.resize(n+1, vector<int>(3, 0));
    cntB.resize(n+1, vector<int>(3, 0));
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 0 ; j < 6 ; j++) {
            v[i][j] = v[i-1][j];
            if(T(a[i-1], b[i-1]) == j)
                v[i][j]++;
        }
    }
    for(int i = 1 ; i <= n ; i++) {
        for(int j = 0 ; j < 3 ; j++) {
            cntA[i][j] = cntA[i-1][j];
            cntB[i][j] = cntB[i-1][j];
            if(j == 0 && a[i-1] == 'A')
                cntA[i][j]++;
            if(j == 1 && a[i-1] == 'T')
                cntA[i][j]++;
            if(j == 2 && a[i-1] == 'C')
                cntA[i][j]++;
            if(j == 0 && b[i-1] == 'A')
                cntB[i][j]++;
            if(j == 1 && b[i-1] == 'T')
                cntB[i][j]++;
            if(j == 2 && b[i-1] == 'C')
                cntB[i][j]++;
        }
    }
}

int get_distance(int x, int y) {
    x++,y++;
    vector<int>t(6);
    for(int i = 0 ; i < 6 ; i++)
        t[i] = v[y][i] - v[x-1][i];
    for(int i = 0 ; i < 3 ; i++) {
        if(cntA[y][i] - cntA[x-1][i] != cntB[y][i] - cntB[x-1][i])
            return -1;
    }
    int ans = 0;
    for(int i = 0 ; i < 6 ; i += 2) {
        int mn = min(t[i], t[i+1]);
        ans += mn;
        t[i] -= mn, t[i+1] -= mn;
    }
    int total = 0;
    for(auto z : t)
        total += z;
    if(total%3)
        return -1;
    ans += (total/3) * 2;
    return ans;
}

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