Submission #1240438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240438		rayan_bd	DNA 돌연변이 (IOI21_dna)	C++20	100 / 100	28 ms	10820 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;

const int mxN = 2e5 + 1000;

string A, B;

int dp[mxN][10];


void init(string a, string b){
	A = a, B = b;
	memset(dp, 0, sizeof(dp));
	for(int i = 1; i <= (int) a.size(); ++i){
		for(int j = 0; j <= 9; ++j) dp[i][j] = dp[i - 1][j];
		dp[i][0] += A[i - 1] == 'A';
		dp[i][0] -= B[i - 1] == 'A';
		dp[i][1] += A[i - 1] == 'C';
		dp[i][1] -= B[i - 1] == 'C';
		dp[i][2] += A[i - 1] == 'T';
		dp[i][2] -= B[i - 1] == 'T';
		dp[i][3] += A[i - 1] == 'A' && B[i - 1] == 'T';
		dp[i][4] += A[i - 1] == 'T' && B[i - 1] == 'A';
		dp[i][5] += A[i - 1] == 'A' && B[i - 1] == 'C';
		dp[i][6] += A[i - 1] == 'C' && B[i - 1] == 'A';
		dp[i][7] += A[i - 1] == 'T' && B[i - 1] == 'C';
		dp[i][8] += A[i - 1] == 'C' && B[i - 1] == 'T';
		dp[i][9] += A[i - 1] == B[i - 1];
	}
}

int get(int x, int y, int t){
	return dp[y][t] - dp[x - 1][t];
}

int get_distance(int x, int y){
	++y, ++x;
	int a = get(x, y, 0), c = get(x, y, 1), t = get(x, y, 2), good = get(x, y, 9), 
	at = get(x, y, 3), ta = get(x, y, 4), ac = get(x, y, 5), ca = get(x, y, 6), tc = get(x, y, 7), ct = get(x, y, 8);
	if(a == 0 && c == 0 && t == 0){
		if(good == (y - x + 1)) return 0;
		int hehehe = ((y - x + 1) - min(at, ta) * 2 - min(ac, ca) * 2 - min(tc, ct) * 2 - good), one = 1, moves = 0, st = 0, en = mxN;
		while(st <= en){
			int mid = st + (en - st) / 2, cost = 0;
			if(mid & 1) cost = (mid + 1) / 2 + mid - 1;
			else  cost = mid / 2 + mid;
			if(cost >= hehehe){
				en = mid - 1;
				moves = mid;
			}else{
				st = mid + 1;
			}
		}
		return min(at, ta) + min(ac, ca) + min(tc, ct) + moves;
	}else{
		return -1;
	}
}

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