Submission #745608

#	Time	Username	Problem	Language	Result	Execution time	Memory
745608		LIF	Mutating DNA (IOI21_dna)	C++17	100 / 100	48 ms	9744 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
#include<string>
using namespace std;
int su[200005][3][3];
int A[200005];
int C[200005];
int T[200005];
int AA[200005];
int CC[200005];
int TT[200005];
void init(std::string a, std::string b) {
	for(int i=0;i<a.length();i++)
	{
		char aa = a[i];
		char bb = b[i];
		int xx = 0;
		if(aa == 'A')
		{
			xx = 1;
			A[i+1] = A[i] + 1;
		}
		else A[i+1] = A[i];
		
		if(aa == 'C')
		{
			xx = 2;
			C[i+1] = C[i] + 1;
		}
		else C[i+1] = C[i];
		
		if(aa == 'T')
		{
			xx = 3;
			T[i+1] = T[i] + 1;
		}
		else T[i+1] = T[i];
		
		int yy = 0;
		if(bb == 'A')
		{
			yy = 1;
			AA[i+1] = AA[i] + 1;
		}
		else AA[i+1] = AA[i];
		
		if(bb == 'C')
		{
			yy = 2;
			CC[i+1] = CC[i] + 1;
		}
		else CC[i+1] = CC[i];
		
		if(bb == 'T')
		{
			yy = 3;
			TT[i+1] = TT[i] + 1;
		}
		else TT[i+1] = TT[i];
		
		for(int j=1;j<=3;j++)
		{
			for(int k=1;k<=3;k++)
			{
				if(j == xx && k == yy)
				{
					su[i+1][j][k] = su[i][j][k] + 1;
				}
				else su[i+1][j][k] = su[i][j][k];
			}
		}
		
	}
}
int get_distance(int x, int y) {
	x += 1;
	y += 1;
	if(A[y] - A[x-1] != AA[y] - AA[x-1])return -1;
	if(C[y] - C[x-1] != CC[y] - CC[x-1])return -1;
	if(T[y] - T[x-1] != TT[y] - TT[x-1])return -1;
	int cnt = 0;
	
	int ans = (y-x+1);
	ans -= (su[y][1][1] - su[x-1][1][1]);
	ans -= (su[y][2][2] - su[x-1][2][2]);
	ans -= (su[y][3][3] - su[x-1][3][3]);
	
	cnt += su[y][1][1] - su[x-1][1][1];
	cnt += su[y][2][2] - su[x-1][2][2];
	cnt += su[y][3][3] - su[x-1][3][3];
	
	int p1 = su[y][1][2] - su[x-1][1][2];
	int p2 = su[y][2][1] - su[x-1][2][1];
	ans -= min(p1,p2);
	cnt += min(p1,p2)*2;
	p1 = su[y][1][3] - su[x-1][1][3];
	p2 = su[y][3][1] - su[x-1][3][1];
	ans -= min(p1,p2);
	cnt += min(p1,p2)*2;
	
	p1 = su[y][2][3] - su[x-1][2][3];
	p2 = su[y][3][2] - su[x-1][3][2];
	ans -= min(p1,p2);
	cnt += min(p1,p2)*2;
	int dd = (y-x+1 - cnt)/3;
	ans -= dd;
	return ans; 
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:13:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0;i<a.length();i++)
      |              ~^~~~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:86:20: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds]
   86 |  ans -= (su[y][3][3] - su[x-1][3][3]);
      |          ~~~~~~~~~~^
dna.cpp:86:36: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds]
   86 |  ans -= (su[y][3][3] - su[x-1][3][3]);
      |                        ~~~~~~~~~~~~^
dna.cpp:96:17: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds]
   96 |  p1 = su[y][1][3] - su[x-1][1][3];
      |       ~~~~~~~~~~^
dna.cpp:96:33: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds]
   96 |  p1 = su[y][1][3] - su[x-1][1][3];
      |                     ~~~~~~~~~~~~^
dna.cpp:97:14: warning: array subscript 3 is above array bounds of 'int [3][3]' [-Warray-bounds]
   97 |  p2 = su[y][3][1] - su[x-1][3][1];
      |       ~~~~~~~^
dna.cpp:97:30: warning: array subscript 3 is above array bounds of 'int [3][3]' [-Warray-bounds]
   97 |  p2 = su[y][3][1] - su[x-1][3][1];
      |                     ~~~~~~~~~^
dna.cpp:101:17: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds]
  101 |  p1 = su[y][2][3] - su[x-1][2][3];
      |       ~~~~~~~~~~^
dna.cpp:101:33: warning: array subscript 3 is above array bounds of 'int [3]' [-Warray-bounds]
  101 |  p1 = su[y][2][3] - su[x-1][2][3];
      |                     ~~~~~~~~~~~~^
dna.cpp:102:14: warning: array subscript 3 is above array bounds of 'int [3][3]' [-Warray-bounds]
  102 |  p2 = su[y][3][2] - su[x-1][3][2];
      |       ~~~~~~~^
dna.cpp:102:30: warning: array subscript 3 is above array bounds of 'int [3][3]' [-Warray-bounds]
  102 |  p2 = su[y][3][2] - su[x-1][3][2];
      |                     ~~~~~~~~~^

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