Submission #838305

#	Time	Username	Problem	Language	Result	Execution time	Memory
838305		SAAD	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	9744 KiB

dna

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

#include "dna.h"
int nm[(int)1e6][3][3] ;
int cma[(int)1e6][3];
int cmb[(int)1e6][3];
void turn ( string&a ){
	int k[120] ;
	k['C'] = 1 , k['T'] = 2 ;
	for(auto&i:a) i = k[i];
}
void init(string a, string b) {
	int n = a.length();
	turn(a);turn(b);
	for (int i = 0; i < n; ++i)
	{
		nm[i][a[i]][b[i]]++;
		cma[i][a[i]]++;
		cmb[i][b[i]]++;
		if ( i ) {
			for ( int j = 0 ; j < 3 ; j++ ) {
				cma[i][j] += cma[i-1][j] ;
				cmb[i][j] += cmb[i-1][j] ;
				for ( int k = 0 ; k < 3 ; k++ ) {
					nm[i][j][k] += nm[i-1][j][k] ;
				}
			}
		}
	}
}

int get_distance(int x, int y) {
	int baqee = 0 , ans = 0 ;
	bool th = true ;
	for ( int i = 0 ; i < 3 ; i++ )  {
		int aa = cma[y][i] - (x?cma[x-1][i]:0) ;
		int bb = cmb[y][i] - (x?cmb[x-1][i]:0) ;
		if ( aa != bb ) th = false ;
	}
	if(!th) return -1 ;
	for ( int i = 0 ; i < 3 ; i++ )  {
		for ( int j = i+1 ; j < 3 ; j++ )  {
			int a = nm[y][i][j] - (x?nm[x-1][i][j]:0) ;
			swap(i,j);
			int b = nm[y][i][j] - (x?nm[x-1][i][j]:0) ;
			swap(i,j);
			int mn = min(a,b);
			ans += mn ;
			a -= mn ; b -= mn ;
			baqee = baqee + a + b ;
		}
	}
	return ((baqee/3)*2) + ans ;
}

Compilation message (stderr)

dna.cpp: In function 'void turn(std::string&)':
dna.cpp:12:22: warning: array subscript has type 'char' [-Wchar-subscripts]
   12 |  for(auto&i:a) i = k[i];
      |                      ^
dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:19:13: warning: array subscript has type 'char' [-Wchar-subscripts]
   19 |   nm[i][a[i]][b[i]]++;
      |             ^
dna.cpp:19:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   19 |   nm[i][a[i]][b[i]]++;
      |                   ^
dna.cpp:20:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |   cma[i][a[i]]++;
      |              ^
dna.cpp:21:14: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |   cmb[i][b[i]]++;
      |              ^

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