제출 #1195735

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195735		Ludissey	DNA 돌연변이 (IOI21_dna)	C++20	56 / 100	879 ms	36764 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
 
using namespace std;
vector<vector<int>> cA,cB;
vector<vector<vector<int>>> tA;
vector<int> A,B;


void init(std::string a, std::string b) {
	cA.clear();
	cB.clear();
	tA.clear();
	A.clear();
	B.clear();
	cA.resize(sz(a)+1,vector<int>(3,0));
	cB.resize(sz(a)+1,vector<int>(3,0));
	tA.resize(sz(a)+1,vector<vector<int>>(3,vector<int>(3,0)));
	A.resize(sz(a)+1,0);
	B.resize(sz(a)+1,0);
	for (int i = 1; i <= sz(a); i++)
	{
		char c=a[i-1];
		if(c=='A') A[i]=0;
		else if(c=='T') A[i]=1;
		else if(c=='C') A[i]=2;
		cA[i][A[i]]++;

		c=b[i-1];
		if(c=='A') B[i]=0;
		else if(c=='T') B[i]=1;
		else if(c=='C') B[i]=2;
		cB[i][B[i]]++;
		if(i>0){
			for (int j = 0; j < 3; j++)
			{
				cA[i][j]+=cA[i-1][j];
				cB[i][j]+=cB[i-1][j];
			}
		}
		tA[i][A[i]][B[i]]++;
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				tA[i][j][k]+=tA[i-1][j][k];
			}
		}
	}
	
}

int get_distance(int x, int y) {
	x++;
	y++;
	for (int j = 0; j < 3; j++)
	{
		cerr <<cA[y][j]-cA[x-1][j]<< "\n";
		cerr <<cB[y][j]-cB[x-1][j]<< "\n";
		if(cA[y][j]-cA[x-1][j]!=cB[y][j]-cB[x-1][j]) return -1;
	}
	int sm=0;
	for (int j = 0; j < 3; j++)
	{
		for (int k = 0; k < 3; k++)
		{
			if(j==k) continue;
			sm+=tA[y][j][k]-tA[x-1][j][k];
		}
	}
	int rem=0;
	for (int j = 0; j < 3; j++)
	{
		for (int k = j+1; k < 3; k++)
		{
			rem+=min(tA[y][j][k]-tA[x-1][j][k],tA[y][k][j]-tA[x-1][k][j]);
		}
	}
	return max(0,(sm-rem*2)-1)+rem;
}

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