Submission #602658

#	Time	Username	Problem	Language	Result	Execution time	Memory
602658		Siffer	Mutating DNA (IOI21_dna)	C++17	100 / 100	53 ms	9524 KiB

dna

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

vector<vector<int>> o;

void init(string a, string b) {
    int n = a.size();
    o.resize(n+1, vector<int>(6,0));
    for(int i = 0; i < n; i++) {
        int k = 0;
        if(a[i]==b[i]) continue;
        if(a[i]=='A' && b[i]=='T') k = 0;
        if(a[i]=='T' && b[i]=='A') k = 1;
        if(a[i]=='C' && b[i]=='A') k = 2;
        if(a[i]=='A' && b[i]=='C') k = 3;
        if(a[i]=='T' && b[i]=='C') k = 4;
        if(a[i]=='C' && b[i]=='T') k = 5;
        o[i+1][k]++;
    }
    for(int i = 0; i < n; i++) for(int j = 0; j < 6; j++) o[i+1][j] += o[i][j];
}

int get_distance(int x, int y) {
    int a = o[y+1][0]-o[x][0]; int b = o[y+1][1]-o[x][1]; int c = o[y+1][2]-o[x][2];
    int d = o[y+1][3]-o[x][3]; int e = o[y+1][4]-o[x][4]; int f = o[y+1][5]-o[x][5];
    if(a-b != c-d || a-b != e-f) return -1;
    return min(a,b)+min(c,d)+min(e,f)+2*abs(a-b);
}

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