Submission #527579

#	Time	Username	Problem	Language	Result	Execution time	Memory
527579		vivaan_gupta	Mutating DNA (IOI21_dna)	C++17	0 / 100	30 ms	4576 KiB

dna

#include "dna.h"
// #include <iostream>
using namespace std;
const int N = 1e5 + 5;
int pre[N];
int n;
int ones[N], ones2[N];

void init(std::string a, std::string b) {
	n = a.size();
	for(int i = 0;i < n;i++){
		int cnt = (a[i] != b[i]);

		pre[i] = cnt;
		ones[i] = (a[i] ==1);
		ones2[i] = (b[i] == 1);
		if(i > 0) {
			pre[i] += pre[i-1];
			ones[i] += ones[i-1];
			ones2[i] += ones2[i-1];
		}
	}
}

int get_distance(int x, int y) {

	int A = ones[y], B = ones2[y];
	if(x > 0) A -= ones[x - 1], B -= ones2[x - 1];
	if(A != B){
		return -1;
	}

	int sum = pre[y];
	if(x > 0) sum -= pre[x - 1]; 
	return (sum / 2);
}

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