Submission #629772

#	Time	Username	Problem	Language	Result	Execution time	Memory
629772		Cross_Ratio	Mutating DNA (IOI21_dna)	C++17	100 / 100	58 ms	9736 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int B[100005][9];
int A[100005][6];
int sum(int x, int y, int type) {
    return B[y-1][type] - (x ? B[x-1][type]:0);
}
int sum2(int x, int y, int type) {
    return A[y-1][type] - (x ? A[x-1][type]:0);
}
map<char,int> M;
int L;
void init(string a, string b) {
    M['A']=0;
    M['T']=1;
    M['C']=2;
    int i, j;
    L = a.length();
    for(i=0;i<L;i++) {
        B[i][3*M[a[i]]+M[b[i]]]++;
    }
    for(i=1;i<L;i++) {
        for(j=0;j<9;j++) B[i][j] += B[i-1][j];
    }
    for(i=0;i<L;i++) {
        A[i][M[a[i]]]++;
        A[i][M[b[i]]+3]++;
    }
    for(i=1;i<L;i++) {
        for(j=0;j<6;j++) A[i][j] += A[i-1][j];
    }
}

int get_distance(int x, int y) {
    y++;
    for(int i = 0; i < 3; i++) {
        if(sum2(x, y, i) != sum2(x, y, i+3)) return -1;
    }
    int ans = 0;
    int ca = sum(x, y, 6);
    int ac = sum(x, y, 2);
    int ta = sum(x, y, 3);
    int at = sum(x, y, 1);
    int ct = sum(x, y, 7);
    int tc = sum(x, y, 5);
    ans += min(ca, ac) + min(ta, at) + min(ct, tc);
    ans += 2*max({max(ca,ac)-min(ca,ac),max(ta,at)-min(ta,at),max(ct,tc)-min(ct,tc)});
    return ans;
}

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