Submission #1108605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108605		sunboi	Mutating DNA (IOI21_dna)	C++17	21 / 100	44 ms	19784 KiB

dna

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

vector<vector<int>> dif, dif2;
vector<vector<int>> match;


void init(string a, string b){
    int n = a.size(); 
    
    dif.clear();
    match.clear();
    dif2.clear();
    dif.resize(n + 1, vector<int> (3));
    dif2.resize(n + 1, vector<int> (3));
    match.resize(n + 1, vector<int> (3));
    
    for (int i = 1; i <= n; i++){
        
        match[i][0] = match[i - 1][0];
        match[i][1] = match[i - 1][1];
        match[i][2] = match[i - 1][2];
        
        
        dif[i][0] = dif[i - 1][0];
        dif[i][1] = dif[i - 1][1];
        dif[i][2] = dif[i - 1][2];
        
        dif2[i][0] = dif2[i - 1][0];
        dif2[i][1] = dif2[i - 1][1];
        dif2[i][2] = dif2[i - 1][2];
        
        if (a[i - 1] == 'A') match[i][0]++;
        else if (a[i - 1] == 'T')match[i][1]++;
        else match[i][2]++;
        
        if (b[i - 1] == 'A') match[i][0]--;
        else if (b[i - 1] == 'T')match[i][1]--;
        else match[i][2]--;
        
        if (a[i - 1] == 'A' && b[i - 1] == 'T') dif[i][0]++;
        else if (a[i - 1] == 'A' && b[i - 1] == 'C')dif[i][1]++;
        else if (a[i - 1] == 'T' && b[i - 1] == 'C') dif[i][2]++;
        
        if (a[i - 1] == 'T' && b[i - 1] == 'A') dif2[i][0]++;
        else if (a[i - 1] == 'C' && b[i - 1] == 'A')dif2[i][1]++;
        else if (a[i - 1] == 'C' && b[i - 1] == 'T') dif2[i][2]++;
    }
}

int get_distance(int x, int y){
    y++;
    x++;
    if (match[y][0] == match[x - 1][0] && match[y][1] == match[x - 1][1] && match[y][2] == match[x - 1][2]){
        int ans = 0;
        int tot = dif[y][0] - dif[x - 1][0] + dif2[y][0] - dif2[x - 1][0];
        int one = min(dif[y][0] - dif[x - 1][0], dif2[y][0] - dif2[x - 1][0]);
        ans += one;
        
        tot += dif[y][1] - dif[x - 1][1] + dif2[y][1] - dif2[x - 1][1];
        int two = min(dif[y][1] - dif[x - 1][1], dif2[y][1] - dif2[x - 1][1]);
        ans += two;
        
        tot += dif[y][2] - dif[x - 1][2] + dif2[y][2] - dif2[x - 1][2];
        int three = min(dif[y][2] - dif[x - 1][2], dif2[y][2] - dif2[x - 1][2]);
        ans += three;
        
        ans += (tot - one - two - three) / 3 * 2;
        return ans;
    }else return -1;
    
}

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