Submission #1089696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089696		versyri	Mutating DNA (IOI21_dna)	C++17	100 / 100	30 ms	8988 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 100005;

int prea[maxn], prec[maxn], pret[maxn];
int prea1[maxn], prec1[maxn], pret1[maxn];

int preac[maxn], preca[maxn], preat[maxn], preta[maxn], prect[maxn], pretc[maxn];
int eq[maxn];
int n;

void init(std::string a, std::string b) {
	memset(prea, 0, sizeof(prea));
	memset(prec, 0, sizeof(prec));
	memset(pret, 0, sizeof(pret));
	memset(prea1, 0, sizeof(prea1));
	memset(prec1, 0, sizeof(prec1));
	memset(pret1, 0, sizeof(pret1));
	memset(preac, 0, sizeof(preac));
	memset(preca, 0, sizeof(preca));
	memset(preat, 0, sizeof(preat));
	memset(preta, 0, sizeof(preta));	
	memset(prect, 0, sizeof(prect));
	memset(pretc, 0, sizeof(pretc));
	memset(eq, 0, sizeof(eq));
	n = a.length();
	for (int i=0;i<n;++i) {
	    int j = i+1;
        prea[j] = prea[j-1];
        prec[j] = prec[j-1];
        pret[j] = pret[j-1];
        prea1[j] = prea1[j-1];
        prec1[j] = prec1[j-1];
        pret1[j] = pret1[j-1];
        preac[j] = preac[j-1];
        preca[j] = preca[j-1];
        preat[j] = preat[j-1];
        preta[j] = preta[j-1];
        prect[j] = prect[j-1];
        pretc[j] = pretc[j-1];
        eq[j] = eq[j-1];
        if (a[i] == 'A') prea[j] += 1;
        if (b[i] == 'A') prea1[j] += 1;
        if (a[i] == 'C') prec[j] += 1;
        if (b[i] == 'C') prec1[j] += 1;
        if (a[i] == 'T') pret[j] += 1;
        if (b[i] == 'T') pret1[j] += 1;
        if (a[i] == 'A' && b[i] == 'C') preac[j] += 1;
        if (a[i] == 'C' && b[i] == 'A') preca[j] += 1;
        if (a[i] == 'A' && b[i] == 'T') preat[j] += 1;
        if (a[i] == 'T' && b[i] == 'A') preta[j] += 1;
        if (a[i] == 'C' && b[i] == 'T') prect[j] += 1;
        if (a[i] == 'T' && b[i] == 'C') pretc[j] += 1;
        if (a[i] == b[i]) eq[j] += 1;
	}
}

int get_distance(int x, int y) {
    x += 1;
    y += 1; 
    if (prea[y] - prea[x-1] != prea1[y] - prea1[x-1]) return -1;
    if (prec[y] - prec[x-1] != prec1[y] - prec1[x-1]) return -1;
    if (pret[y] - pret[x-1] != pret1[y] - pret1[x-1]) return -1;
    int tot = y-x+1 - (eq[y] - eq[x-1]);
    int acm = min(preac[y]-preac[x-1], preca[y]-preca[x-1]);
    int atm = min(preat[y]-preat[x-1], preta[y]-preta[x-1]);
    int ctm = min(prect[y]-prect[x-1], pretc[y]-pretc[x-1]);
    tot -= 2*acm;
    tot -= 2*atm;
    tot -= 2*ctm;
    int ans = acm+atm+ctm;
    ans += tot / 3 * 2;
	return ans;
}

// int main() {
//     init("ABA", "ABA");
//     // std::cout << get_distance(0, 2) << std::endl;
//     // std::cout << get_distance(4, 5) << std::endl;
//     // std::cout << get_distance(3, 5) << std::endl; 

//     return 0;
// }

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