Submission #468044

#	Time	Username	Problem	Language	Result	Execution time	Memory
468044		imas_713_a	Mutating DNA (IOI21_dna)	C++17	35 / 100	56 ms	8576 KiB

dna

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

#include "dna.h"

# define ll long long

vector<ll> at(100001),ta(100001),ac(100001),ca(100001),tc(100001),ct(100001);

void init(std::string a, std::string b) {
  ll s=a.size();
	  for(int i=0; i<s; i++){
		  string ty;
		  ty+=a[i];
		  ty+=b[i];
		  if(ty=="AT")at[i+1]=at[i]+1;
		  else
			  at[i+1]=at[i];
		  if(ty=="TA") ta[i+1]=ta[i]+1;
		  else
			  ta[i+1]=ta[i];
		  if(ty=="AC") ac[i+1]=ac[i]+1;
		  else
			  ac[i+1]=ac[i];
		  if(ty=="CA") ca[i+1]=ca[i]+1;
		  else
			  ca[i+1]=ca[i];
		  if(ty=="TC") tc[i+1]=tc[i]+1;
		  else
              tc[i+1]=tc[i];
		  if(ty=="CT") ct[i+1]=ct[i]+1;
		  else
			  ct[i+1]=ct[i];
	  }
}
int get_distance(int x, int y) {
	x++;
	y++;
	ll AT=at[y]-at[x-1],TA=ta[y]-ta[x-1],AC=ac[y]-ac[x-1],CA=ca[y]-ca[x-1],TC=tc[y]-tc[x-1],CT=ct[y]-ct[x-1];
	ll pos1a=AT+AC,pos1t=TA+TC,pos1c=CA+CT;
	ll pos2a=TA+CA,pos2t=AT+CT,pos2c=AC+TC;
	if(pos1a!=pos2a || pos1c!=pos2c || pos1t!=pos2t) return -1;
	  ll ans=AT+TA+AC+CA+TC+CT;
	  ll once=0;
	  once+=min(AT,TA);
	  AT-=min(AT,TA);
	  TA-=min(AT,TA);
	  once+=min(AC,CA);
	  AT-=min(AC,CA);
	  TA-=min(AC,CA);
	  once+=min(TC,CT);
	  AT-=min(TC,CT);
	  TA-=min(TC,CT);
	  once+=min({AT,CA,TC});
	  once+=min({TA,AC,CT});
	  return ans-once;
}

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