Submission #1009323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009323		aParrot	Mutating DNA (IOI21_dna)	C++17	0 / 100	18 ms	3612 KiB

dna

#include "bits/stdc++.h"
#include "dna.h"
using namespace std;
// const int N = 100000;
const int N = 6;

bitset<N> bita, bitb;


void print_bitset(bitset<N> b) {
	for (int i=0; i<N; i++) {
		cout << b[i];
	}
	cout << endl;
}


void init(string a, string b) {
	for (int i=0; i<(int)a.length(); i++) {
		bita[i] = a[i] == 'B';
		bitb[i] = b[i] == 'B';
	}

	// cout << "init:" << endl;
	// print_bitset(bita);
	// print_bitset(bitb);
	// cout << endl;
}

int get_distance(int x, int y) {
	// // brute force not finished
	// int c = 0;
	// int last = y;
	// for (int i=x; i<=y; i++) {
	// 	if (a[i] == b[i]) {
	// 		continue;
	// 	} else {
	// 		// a[i] != b[i]
	// 		// find last j <= such that a[i] == b[j]
	// 		for (int j=last; j>i; j--) {

 	// 	}
	//   }
	// }

	int len = y-x+1;
	bitset<N> ones = (1<<len)-1;
	
	bitset<N> ra = (bita >> x) & ones;
	int acount = ra.count();

	bitset<N> rb = (bitb >> x) & ones;
	int bcount = ra.count();

	// number of B's in 
	if (acount != bcount) {
		return -1;
	}

	// find number of overlapping
	int overlap = (ra&rb).count();
	int distance = acount - overlap;
	return distance;

	
	// cout << "len: " << len << endl;
	// cout << "ones" << endl;
	// print_bitset(ones);
	// cout << "acount: " << acount << endl;
	// cout << "bcount: " << bcount << endl;
	// cout << "overlap: " << overlap << endl;
	// cout << distance << endl;
}

// int main() {
// 	// init("AAABBB", "BBBAAA");
// 	init("ATACAT", "ACTATA");
// 	get_distance(1, 3);
// 	get_distance(4, 5);
// 	get_distance(3, 5);

// 	return 0;
// }

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