Submission #1129180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129180		Matbubble	Mutating DNA (IOI21_dna)	C++20	56 / 100	91 ms	15432 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<": "<<x<<"\n";
using namespace std;
const int maxN=1e5+10;
int tree[4*maxN][10];
int curr[10];
int prefA[maxN+10][3], prefB[maxN+10][3];
string A, B;
int hashi(char a, char b){
	int num=3*(a-'A')+(b-'A');
	return num;
}

void build(int root, int l, int r){
	if(l==r){
		tree[root][hashi(A[l], B[r])]++;
		return;
	}
	int mid=((l+r)>>1);
	build(2*root, l, mid);
	build(2*root+1, mid+1, r);
	for(int i=0 ; i<9 ; i++) tree[root][i]=tree[2*root][i]+tree[2*root+1][i];
}

void querie(int root, int l, int r, int ql, int qr){
	if(r<ql || l>qr) return;
	if(l>=ql && r<=qr){
		// dbg(l)
		// dbg(r)
		for(int i=0 ; i<9 ; i++) curr[i]+=tree[root][i];
		return;
	}
	int mid=((l+r)>>1);
	querie(2*root, l, mid, ql, qr);
	querie(2*root+1, mid+1, r, ql, qr);
}

void init(std::string a, std::string b) {
	for(char &ch:a){
		if(ch=='T') ch='B';
	}
	for(char &ch:b){
		if(ch=='T') ch='B';
	}
	// return;
	A=a;
	B=b;
	build(1, 0, (int)a.size()-1);
	for(int i=1 ; i<=(int)a.size() ; i++){
		if(i>1){
			for(int j=0 ; j<3 ; j++){
				prefA[i][j]=prefA[i-1][j];
				prefB[i][j]=prefB[i-1][j];
			}
		}
		int sumA=a[i-1]-'A', sumB=b[i-1]-'A';
		prefA[i][sumA]++;
		prefB[i][sumB]++;
	}
}

int get_distance(int x, int y) {
	// return 0;
	for(int i=0 ; i<3 ; i++){
		if(prefA[y+1][i]-prefA[x][i]!=prefB[y+1][i]-prefB[x][i]) return -1;
	}
	for(int i=0 ; i<9 ; i++) curr[i]=0;
	// dbg(x)
	// dbg(y)
	querie(1, 0, (int)A.size()-1, x, y);
	int ans=0, need=0;
	// for(int i=0 ; i<9 ; i++) dbg(curr[i])
	for(int i=0 ; i<9 ; i++){
		int izq=i/3, der=i%3;
		if(izq==der) continue;
		int aux=min(curr[i], curr[3*der+izq]);
		ans+=aux;
		curr[i]-=aux;
		curr[3*der+izq]-=aux;
		need+=curr[i];
	}
	assert(need==3 || need==0);
	return ans+(need>0?2:0);
}

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