Submission #1084333

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084333		randomasshandle	Mutating DNA (IOI21_dna)	C++17	56 / 100	30 ms	7060 KiB

dna

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

int Aa[100001], Ta[100001], Ca[100001], Ab[100001], Tb[100001], Cb[100001], diff[100001];
string A, B;
void init(string a, string b){
    A = a;
    B = b;
    a = a + 'f';
    b = b + 'f';
    if(a[0] == 'A') Aa[0] = 1;
    if(a[0] == 'T') Ta[0] = 1;
    if(a[0] == 'C') Ca[0] = 1;
    if(b[0] == 'A') Ab[0] = 1;
    if(b[0] == 'T') Tb[0] = 1;
    if(b[0] == 'C') Cb[0] = 1;
    if(a[0] != b[0]) diff[0] = 1;
    for(int i = 1; i <= (int)a.length(); i++){
        Aa[i] = Aa[i - 1];
        Ta[i] = Ta[i - 1];
        Ca[i] = Ca[i - 1];
        Ab[i] = Ab[i - 1];
        Tb[i] = Tb[i - 1];
        Cb[i] = Cb[i - 1];
        diff[i] = diff[i - 1];
        if(a[i] == 'A') Aa[i] = Aa[i - 1] + 1;
        if(a[i] == 'T') Ta[i] = Ta[i - 1] + 1;
        if(a[i] == 'C') Ca[i] = Ca[i - 1] + 1;
        if(b[i] == 'A') Ab[i] = Ab[i - 1] + 1;
        if(b[i] == 'T') Tb[i] = Tb[i - 1] + 1;
        if(b[i] == 'C') Cb[i] = Cb[i - 1] + 1;
        if(a[i] != b[i]) diff[i] = diff[i - 1] + 1;
    }
}


int get_distance(int x, int y){
    int big = x == 0 ? 0 : Aa[x-1];
    //cerr<<"abig "<<Aa[y + 1]<<endl;
    int cnt_aa = Aa[y] - big;
    big = x == 0 ? 0 : Ta[x-1];
    int cnt_ta = Ta[y] - big;
    big = x == 0 ? 0 : Ca[x-1];
    int cnt_ca = Ca[y] - big;
     big = x == 0 ? 0 : Ab[x-1];
    int cnt_ab = Ab[y] - big;
     big = x == 0 ? 0 : Tb[x-1];
    int cnt_tb = Tb[y] - big;
     big = x == 0 ? 0 : Cb[x-1];
    int cnt_cb = Cb[y] - big;
    //cerr<<cnt_aa<<" "<<cnt_ab<<" ";
    if(cnt_aa != cnt_ab || cnt_ta != cnt_tb || cnt_ca != cnt_cb) return -1;
    big = x == 0 ? 0 : diff[x - 1];
    int df = diff[y] - big;
    //cerr<<df<<" "<<big<<endl;
    int mid = df / 2;
    return df % 2 == 0 ? mid : mid + 1; 
}

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