Submission #735116

#	Time	Username	Problem	Language	Result	Execution time	Memory
735116		Cutebol	Mutating DNA (IOI21_dna)	C++17	56 / 100	46 ms	5924 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std ;
const int N = 1e5 + 5 ;
int a[N] , t[N] , c[N] , a1[N] , t1[N] , c1[N] ;
int pref[N] ;
void init( string x , string y ) {
	int n = x.size() ;
	for ( int i = 0 ; i < n ; i ++ ){
		pref[i] = ( x[i] != y[i] ) ;
		a[i] = ( x[i] == 'A' ) ;
		c[i] = ( x[i] == 'C' ) ;
		t[i] = ( x[i] == 'T' ) ;
		a1[i] = ( y[i] == 'A' ) ;
		c1[i] = ( y[i] == 'C' ) ;
		t1[i] = ( y[i] == 'T' ) ;
		if (i){
			pref[i] += pref[i-1] ;
			a[i] += a[i-1] ;
			c[i] += c[i-1] ;
			t[i] += t[i-1] ;
			a1[i] += a1[i-1] ;
			c1[i] += c1[i-1] ;
			t1[i] += t1[i-1] ;
		}
	}
}

int get_distance(int x, int y) {
	
	int d = pref[y] ;
	if (x) d -= pref[x-1] ;
	int sum = ( a[y] - a1[y] ) ;
	if (x) sum += ( a1[x-1] - a[x-1] ) ;
	if (sum!=0) return -1 ;
	sum = ( c[y] - c1[y] ) ;
	if (x) sum += ( c1[x-1] - c[x-1] ) ;
	if (sum!=0) return -1 ;
	sum = ( t[y] - t1[y] ) ;
	if (x) sum += ( t1[x-1] - t[x-1] ) ;
	if (sum!=0) return -1 ;
	return (d+1)/2 ;
}

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