Submission #1064648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064648		glupan	Mutating DNA (IOI21_dna)	C++17	35 / 100	33 ms	8956 KiB

dna

#include <bits/stdc++.h>

using namespace std;

string a,b;
int n;
int cntA[2][100005], cntC[2][100005], cntT[2][100005], pref[6][100005];

void init(string A, string B) {
    a = A;
    b = B;
    n = a.length();
    memset(pref,0,sizeof pref);
    memset(cntA,0,sizeof cntA);
    memset(cntC,0,sizeof cntC);
    memset(cntT,0,sizeof cntT);
    for(int i=0; i<n; i++) {
        if(a[i] != b[i]) {
            if(a[i] == 'A') {
                if(b[i] == 'T')
                    pref[0][i]++;
                else if(b[i] == 'C')
                    pref[1][i]++;
            }
            else if(a[i] == 'T') {
                if(b[i] == 'A')
                    pref[2][i]++;
                else if(b[i] == 'C')
                    pref[3][i]++;
                }
            else if(a[i] == 'C') {
                if(b[i] == 'A')
                    pref[4][i]++;
                else if(b[i] == 'T')
                    pref[5][i]++;
            }
        }
        if(a[i] == 'A')
            cntA[0][i]++;
        else if(a[i] == 'C')
            cntC[0][i]++;
        else if(a[i] == 'T')
            cntT[0][i]++;
        if(b[i] == 'A')
            cntA[1][i]++;
        else if(b[i] == 'C')
            cntC[1][i]++;
        else if(b[i] == 'T')
            cntT[1][i]++;
        if(i) {
            pref[0][i]+=pref[0][i-1];
            pref[1][i]+=pref[1][i-1];
            pref[2][i]+=pref[2][i-1];
            pref[3][i]+=pref[3][i-1];
            pref[4][i]+=pref[4][i-1];
            pref[5][i]+=pref[5][i-1];
            cntA[0][i]+=cntA[0][i-1];
            cntC[0][i]+=cntC[0][i-1];
            cntT[0][i]+=cntT[0][i-1];
            cntA[1][i]+=cntA[1][i-1];
            cntC[1][i]+=cntC[1][i-1];
            cntT[1][i]+=cntT[1][i-1];
        }
    }
}

int get_distance(int x, int y) {
    int numA[2], numC[2], numT[2];
    numA[0] = cntA[0][y];
    numC[0] = cntC[0][y];
    numT[0] = cntT[0][y];
    if(x) {
        numA[0]-=cntA[0][x-1];
        numC[0]-=cntC[0][x-1];
        numT[0]-=cntT[0][x-1];
    }
    numA[1] = cntA[1][y];
    numC[1] = cntC[1][y];
    numT[1] = cntT[1][y];
    if(x) {
        numA[1]-=cntA[1][x-1];
        numC[1]-=cntC[1][x-1];
        numT[1]-=cntT[1][x-1];
    }
    if(numA[0] != numA[1] or numC[0] != numC[1] or numT[0] != numT[1])
        return -1;
    int cnt[6];
    for(int i=0; i<6; i++)
        cnt[i] = pref[i][y];
    if(x)
        for(int i=0; i<6; i++)
            cnt[i]-=pref[i][x-1];
    return (max(cnt[0],cnt[2])+max(cnt[1],cnt[4])+max(cnt[3],cnt[5]));
}

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