Submission #1058537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058537		pcc	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	7872 KiB

dna

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

const int mxn = 1e5+10;
const int B = 7;

int pref[mxn][B];
int cnt[mxn][3];

int tp(char a,char b){
	if(a == b)return 0;
	int re = 0;
	if(a == 'A'&&b == 'T')return 1;
	if(a == 'A'&&b == 'C')return 2;
	if(a == 'T'&&b == 'A')return 3;
	if(a == 'T'&&b == 'C')return 4;
	if(a == 'C'&&b == 'A')return 5;
	if(a == 'C'&&b == 'T')return 6;
	assert(false);
}

void init(std::string a, std::string b) {
	a = "#"+a,b = "#"+b;
	for(int i = 1;i<a.size();i++){
		for(int j = 0;j<3;j++)cnt[i][j] = cnt[i-1][j];
		if(a[i] == 'A')cnt[i][0]++;
		else if(a[i] == 'T')cnt[i][1]++;
		else cnt[i][2]++;
		if(b[i] == 'A')cnt[i][0]--;
		else if(b[i] == 'T')cnt[i][1]--;
		else cnt[i][2]--;
		for(int j = 0;j<B;j++){
			pref[i][j] = pref[i-1][j];
		}
		pref[i][tp(a[i],b[i])]++;
	}
	return;
}

int get_distance(int x, int y) {
	x++,y++;
	for(int i = 0;i<3;i++){
		if(cnt[y][i]-cnt[x-1][i] != 0)return -1;
	}
	int rest[B] = {};
	for(int i = 1;i<B;i++)rest[i] = pref[y][i]-pref[x-1][i];
	int ans = 0;
	int d;
	d = min(rest[1],rest[3]);ans += d,rest[1] -= d,rest[3] -= d;
	d = min(rest[2],rest[5]);ans += d,rest[2] -= d,rest[5] -= d;
	d = min(rest[4],rest[6]);ans += d;rest[4] -= d,rest[6] -= d;
	int non = 0;
	for(auto &i:rest)if(i)non = i;
	for(auto &i:rest)if(i)assert(non == i);
	ans += non<<1;
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int tp(char, char)':
dna.cpp:13:6: warning: unused variable 're' [-Wunused-variable]
   13 |  int re = 0;
      |      ^~
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:25:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 1;i<a.size();i++){
      |                ~^~~~~~~~~

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