제출 #739754

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739754		Trumling	DNA 돌연변이 (IOI21_dna)	C++17	21 / 100	45 ms	11872 KiB

dna

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

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

ll pre[3][100002];
vector<vector<vector<int>>>nums(2,vector<vector<int>>(3,vector<int>(100002)));
vector<vector<vector<int>>>other(3,vector<vector<int>>(3,vector<int>(100002)));

void init(string a,string b) 
{
	ll n=a.size();
	int cc[26]={ };

	cc[0]=0;
	cc['T'-'A']=1;
	cc['C'-'A']=2;

	for(int i=1;i<=n;i++)
	{
		ll aa=cc[a[i-1]-'A']; 
		ll bb=cc[b[i-1]-'A'];
		for(int j=0;j<3;j++)
			pre[j][i]=pre[j][i-1];

		for(int j=0;j<3;j++)
			for(int c=0;c<3;c++)
			{
				other[j][c][i]=other[j][c][i-1];
				if(j!=2)
				nums[j][c][i]=nums[j][c][i-1];
			}

		nums[0][aa][i]++;
		nums[1][bb][i]++;

		if(a[i-1]==b[i-1])
		continue;
		pre[aa][i]++;

		other[bb][aa][i]++;
	}

}

int get_distance(int x, int y) 
{
	x++;
	y++;

	for(int i=0;i<3;i++)
	if(nums[0][i][y]-nums[0][i][x-1]!=nums[1][i][y]-nums[1][i][x-1])
	return -1;
	ll ac=0,ca=0,at=0,ta=0,ct=0,tc=0;

 	ac=other[2][0][y]-other[2][0][x-1];
	ca=other[0][2][y]-other[0][2][x-1];

	at=other[1][0][y]-other[1][0][x-1];
	ta=other[0][1][y]-other[0][1][x-1];

	ct=other[1][2][y]-other[1][2][x-1];
	tc=other[2][1][y]-other[2][1][x-1];

	//cout<<max(ac,ca) <<' '<< max(at,ta) <<' '<< max(ct,tc);
	return min(at,ta) + min(ca,ac) + min(ct,tc) + ( at + tc + ta + ct + ac + ca-(min(at,ta) + min(ca,ac) + min(ct,tc)))/3*2;

}

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