Submission #438540

#	Time	Username	Problem	Language	Result	Execution time	Memory
438540		Stickfish	Mutating DNA (IOI21_dna)	C++17	21 / 100	44 ms	5828 KiB

dna

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

const int MAXN = 1e5 + 123;
int pfbad_[MAXN];
int* pfbad;

int pfcnt__[MAXN][3];
int* pfcnt_[MAXN];
int** pfcnt = (pfcnt_ + 1);

vector<int> cnvt(string a){
	int n = a.size();
	vector<int> ans(n);
	for(int i = 0; i < n; ++i){
		if(a[i] == 'A')
			ans[i] = 0;
		if(a[i] == 'C')
			ans[i] = 1;
		if(a[i] == 'T')
			ans[i] = 2;
	}
	return ans;
}

void init(string a_, string b_){
	for(int i = 0; i < MAXN; ++i)
		pfcnt_[i] = pfcnt__[i];
	pfcnt = pfcnt_ + 1;
	pfbad = pfbad_ + 1;

	vector<int> a = cnvt(a_);
	vector<int> b = cnvt(b_);
	int n = a.size();
	
	for(int i = 0; i < n; ++i){
		pfbad[i] = pfbad[i - 1];
		for(int j = 0; j < 3; ++j){
			pfcnt[i][j] = pfcnt[i - 1][j];
		}
		if(a[i] != b[i]){
			++pfbad[i];
			++pfcnt[i][a[i]];
			--pfcnt[i][b[i]];
		}
	}
}

int get_distance(int x, int y) {
	++y;
	for(int i = 0; i < 3; ++i){
		if(pfcnt[y - 1][i] - pfcnt[x - 1][i] != 0)
			return -1;
	}
	return max(pfbad[y - 1] - pfbad[x - 1] - 1, 0);
}

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