Submission #1198741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198741		alenhsiao	Mutating DNA (IOI21_dna)	C++20	0 / 100	19 ms	4608 KiB

dna

#include "dna.h"
#include <vector>
using namespace std;

vector<int> AC, AT, CA, CT, TA, TC;
void init(std::string a, std::string b) {
	int n = a.size();
	AC.resize(n+1);
	AT.resize(n+1);
	CA.resize(n+1);
	CT.resize(n+1);
	TA.resize(n+1);
	TC.resize(n+1);
	for (int i = 0; i < n; i++) {
		if (a[i] == 'A' && b[i] == 'C') AC[i+1] = AC[i] + 1;
		if (a[i] == 'A' && b[i] == 'T') AT[i+1] = AT[i] + 1;
		if (a[i] == 'C' && b[i] == 'A') CA[i+1] = CA[i] + 1;
		if (a[i] == 'C' && b[i] == 'T') CT[i+1] = CT[i] + 1;
		if (a[i] == 'T' && b[i] == 'A') TA[i+1] = TA[i] + 1;
		if (a[i] == 'T' && b[i] == 'C') TC[i+1] = TC[i] + 1;
	}
}

int get_distance(int x, int y) {
        
        int ac = AC[y + 1] - AC[x];
        int at = AT[y + 1] - AT[x];
        int ca = CA[y + 1] - CA[x];
        int ct = CT[y + 1] - CT[x];
        int ta = TA[y + 1] - TA[x];
        int tc = TC[y + 1] - TC[x];
        if (ac + at != ca + ta || ca + ct != ac + tc || ta + tc != at + ct) {
            return -1;
        }

        int swap1 = min(ac, ca); ac -= swap1; ca -= swap1;
        int swap2 = min(at, ta); at -= swap2; ta -= swap2;
        int swap3 = min(ct, tc); ct -= swap3; tc -= swap3;

        int cycle = ac + ca; 
        int ans = swap1 + swap2 + swap3 + 2 * cycle;
        return ans;
}

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