제출 #744663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744663		Ocean_MO	DNA 돌연변이 (IOI21_dna)	C++17	35 / 100	96 ms	15804 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define inf LLONG_MAX
#define pll pair<ll,ll>
#define pb push_back

// O n*q
ll asum[3][100005]={},bsum[3][100005]={},indeg[3][3][100005]={};//01=A, 23=C, 45=T
ll n;
string aa,bb;
int turn(char c){
	if(c=='A')return 0;
	if(c=='C')return 1;
	return 2;
}
void init(std::string a, std::string b) {
	n=a.size();
	aa=a;
	bb=b;
	for(ll i=0;i<n;i++){
		for(ll j=0;j<3;j++)asum[j][i+1]=asum[j][i];
		for(ll j=0;j<3;j++)bsum[j][i+1]=bsum[j][i];
		asum[turn(a[i])][i+1]++;
		bsum[turn(b[i])][i+1]++;
	}
	for(ll i=0;i<n;i++){
		for(ll j=0;j<3;j++){
			for(ll k=0;k<3;k++)indeg[j][k][i+1]=indeg[j][k][i];
		}
		if(b[i]!=a[i]){
			indeg[turn(b[i])][turn(a[i])][i+1]++;
		}
	}
}

ll l;
int get_distance(int x, int y) {
	for(ll i=0;i<3;i++){
		ll temp=asum[i][y+1]-asum[i][x],temp2=bsum[i][y+1]-bsum[i][x];
		if(temp!=temp2)return -1;
	}
	ll ans=0;
	ll buff[3][3]={};
	for(ll i=0;i<3;i++){
		for(ll j=0;j<3;j++){
			buff[i][j]=indeg[i][j][y+1]-indeg[i][j][x];
		}
	}
	for(ll i=0;i<3;i++){
		for(ll j=0;j<3;j++){
			if(i==j)continue;
			ll temp=min(buff[i][j],buff[j][i]);
			ans+=temp;
			buff[i][j]-=temp;
			buff[j][i]-=temp;
		}
	}
	for(ll i=0;i<3;i++){
		for(ll j=0;j<3;j++){
			if(buff[i][j]!=0){
				ans+=2*buff[i][j];
				break;
			}
		}
	}
	return ans;
}

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