Submission #437104

#	Time	Username	Problem	Language	Result	Execution time	Memory
437104		whaleee	Mutating DNA (IOI21_dna)	C++17	100 / 100	56 ms	7660 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
 
int n;
int prefix_cnt_a[100000+1][3];
int prefix_cnt_b[100000+1][3];
int pairs_cnt[100000+1][7];
// int pairs_cnt_b[100000+1][3];
char lst[6][2] = {{'T', 'C'}, {'C', 'T'}, {'A', 'T'}, {'T', 'A'}, {'A', 'C'}, {'C', 'A'}};
 
using namespace std;
 
void init(std::string a, std::string b) {
	n = a.size();
	for(int i=0; i<3; i++) {
		prefix_cnt_a[0][i]=0; 
		prefix_cnt_b[0][i]=0;
		// pairs_cnt_b[0][i]=0;
	}
	for(int i=0; i<6; i++) {
		pairs_cnt[0][i] = 0;
	}
	int bonus;
	int dc,da,dt;
	// int tc,ct,at,ta,ac,ca;
	for(int i=0; i<n;i++) {
		dc=0;da=0;dt=0;
		if (a[i] == 'C') dc=1;
		if (a[i] == 'A') da=1;
		if (a[i] == 'T') dt=1;
		prefix_cnt_a[i+1][0] = prefix_cnt_a[i][0]+dc;
		prefix_cnt_a[i+1][1] = prefix_cnt_a[i][1]+da;
		prefix_cnt_a[i+1][2] = prefix_cnt_a[i][2]+dt;
		dc=0;da=0;dt=0;
		if (b[i] == 'C') dc=1;
		if (b[i] == 'A') da=1;
		if (b[i] == 'T') dt=1;
		prefix_cnt_b[i+1][0] = prefix_cnt_b[i][0]+dc;
		prefix_cnt_b[i+1][1] = prefix_cnt_b[i][1]+da;
		prefix_cnt_b[i+1][2] = prefix_cnt_b[i][2]+dt;
 
		dc=0;da=0;dt=0;
		for (int j=0; j <6; j++) {
			bonus = 0;
			if (a[i] == lst[j][0] && b[i] == lst[j][1]) bonus=1;
			pairs_cnt[i+1][j] = pairs_cnt[i][j] + bonus;
		}
		bonus =0;
		if (a[i] == b[i]) bonus=1;
		pairs_cnt[i+1][6] = pairs_cnt[i][6] + bonus;
		// if (a[i] == 'T' && b[i])
 
	}	
}
 
int get_distance(int x, int y) {
	// cerr << "START\n";
	// cerr << a[x];
	for (int i=0; i<3; i++) {
		// cerr << prefix_cnt_a[y+1][i] << ',' << prefix_cnt_a[x][i] << "," << prefix_cnt_b[y+1][i] << "," <<  prefix_cnt_b[x][i] << '\n';
		if (prefix_cnt_a[y+1][i]-prefix_cnt_a[x][i] != prefix_cnt_b[y+1][i] - prefix_cnt_b[x][i]) {
			return -1;
		}
	}
	// cerr << "HERE\n";
	int tc = pairs_cnt[y+1][0] - pairs_cnt[x][0];
	int ct = pairs_cnt[y+1][1] - pairs_cnt[x][1];
	int at = pairs_cnt[y+1][2] - pairs_cnt[x][2];
	int ta = pairs_cnt[y+1][3] - pairs_cnt[x][3];
	int ac = pairs_cnt[y+1][4] - pairs_cnt[x][4];
	int ca = pairs_cnt[y+1][5] - pairs_cnt[x][5];
	int correct = pairs_cnt[y+1][6] - pairs_cnt[x][6];
 
	int l = y-x + 1;
	int ans = min(tc,ct) + min(at,ta) + min(ac,ca);
	// cerr <<  min(tc,ct)  << "," << min(at,ta) << "," << min(ac,ca) << '\n';
	int rest = l - 2*ans - correct;
	// cerr << "length: " << l  << " and " << rest << "bonus +  " <<(rest+2)/3 <<  '\n';
	ans += 2*(rest/3);
	return ans;
}

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