Submission #438192

#	Time	Username	Problem	Language	Result	Execution time	Memory
438192		dacin21	Mutating DNA (IOI21_dna)	C++17	100 / 100	65 ms	6312 KiB

dna

#include "dna.h"

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

int n;
vector<array<int, 9> > pre;

template<typename T, size_t s>
array<T, s> operator-(array<T, s> a, array<T, s> const&b){
    for(size_t i = 0; i < s; ++i){
        a[i] -= b[i];
    }
    return a;
}

int deco(char const c){
    switch(c){
        case 'A':
            return 0;
        case 'T':
            return 1;
        case 'C':
            return 2;
        default:
            assert(0);
            return -1;
    }
}

void init(string a, string b) {
    n = a.size();
    pre.assign(n+1, array<int, 9>{});
    for(int i=0; i<n; ++i){
        pre[i+1] = pre[i];
        ++pre[i+1][deco(a[i])*3+deco(b[i])];
    }
}

int get_distance(int x, int y) {
    auto tmp = pre[y+1] - pre[x];
    int ret = 0;
    for(int i:{0,1,2}){
        const int j = (i+1)%3;
        const int x = min(tmp[3*i+j], tmp[3*j+i]);
        ret += x;
        tmp[3*i+j] -= x;
        tmp[3*j+i] -= x;
    }
    if(tmp[3*0+1] != tmp[3*1+2] || tmp[3*0+1] != tmp[3*2+0]){
        return -1;
    }
    if(tmp[3*1+0] != tmp[3*2+1] || tmp[3*1+0] != tmp[3*0+2]){
        return -1;
    }
    ret += 2*tmp[3*0+1];
    ret += 2*tmp[3*0+2];
    return ret;
}

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