Submission #979968

#	Time	Username	Problem	Language	Result	Execution time	Memory
979968		batsukh2006	Mutating DNA (IOI21_dna)	C++17	100 / 100	45 ms	9836 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
const int mxN=1e5+1;
int mp[mxN][3][3];
int f[mxN][3],s[mxN][3];
void init(string a, string b){
	map<char,int> m;
	m['A']=0;
	m['T']=1;
	m['C']=2;
	for(int i=1; i<=a.size(); i++){
		for(int j=0; j<3; j++){
			f[i][j]=f[i-1][j];
			s[i][j]=s[i-1][j];
			for(int k=0; k<3; k++){
				mp[i][j][k]=mp[i-1][j][k];
			}
		}
		f[i][m[a[i-1]]]++;
		s[i][m[b[i-1]]]++;
		mp[i][m[a[i-1]]][m[b[i-1]]]++;
	}
}
int get_distance(int x, int y){
	for(int i=0; i<3; i++){
		if(f[y+1][i]-f[x][i]!=s[y+1][i]-s[x][i]){
			return -1;
		}
	}
  	int ans=0;
	int lft=y-x+1;
	for(int i=0; i<3; i++){
		for(int j=i; j<3; j++){
			if(i==j) lft-=min(mp[y+1][i][j]-mp[x][i][j],mp[y+1][j][i]-mp[x][j][i]);
			else lft-=2*min(mp[y+1][i][j]-mp[x][i][j],mp[y+1][j][i]-mp[x][j][i]);
			if(i!=j) ans+=min(mp[y+1][i][j]-mp[x][i][j],mp[y+1][j][i]-mp[x][j][i]);
		}
	}
	return ans+lft/3*2;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  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