Submission #717876

#	Time	Username	Problem	Language	Result	Execution time	Memory
717876		duchuy297	Mutating DNA (IOI21_dna)	C++17	100 / 100	39 ms	9768 KiB

dna

#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int cnt[2][N][3];
int dif[N][3][3];
int dak[500];
void init(string a, string b) {
	int n = a.size();
	a = "?" + a;
	b = "?" + b;
	dak['A'] = 0;
	dak['T'] = 1;
	dak['C'] = 2;
	for (int i=1; i<=n; i++) {
		for (int j=0; j<3; j++) {
			cnt[0][i][j] = cnt[0][i-1][j];
			cnt[1][i][j] = cnt[1][i-1][j];
		}
		cnt[0][i][dak[a[i]]]++;
		cnt[1][i][dak[b[i]]]++;
		for (int j=0; j<3; j++) {
			for (int k=0; k<3; k++) {
				dif[i][j][k] = dif[i-1][j][k] + (dak[a[i]] == j && dak[b[i]] == k);
			}
		}
	}
}
int get (int id, int l, int r, int u) {
	return cnt[id][r][u] - cnt[id][l-1][u];
}
int get_dif (int l, int r, int u, int v) {
	return dif[r][u][v] - dif[l-1][u][v];
}
int get_distance(int l, int r) {
	l++; r++;
	for (int i=0; i<3; i++) if (get(0,l,r,i) != get (1,l,r,i)) return -1;
	int cnt = r -l + 1;
	int res = 0;
	for (int i=0; i<3; i++) {
		cnt -= get_dif (l,r,i,i);
		for (int j=0; j<i; j++) {
			int val = min (get_dif(l,r,i,j), get_dif(l,r,j,i));
			res += val;
			cnt -= val*2;
		}
	}
	assert(cnt%3==0);
//	cout << cnt << " ??\n";
	res += cnt/3*2;
	return res;
}
/*int main() {
	string a,b; cin >> a >> b;
	init(a,b);
	int q; cin >> q;
	while (q--) {
		int l,r; cin >> l >> r;
		cout << get_distance(l,r) << '\n'; 
	}
}*/

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:20:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |   cnt[0][i][dak[a[i]]]++;
      |                     ^
dna.cpp:21:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |   cnt[1][i][dak[b[i]]]++;
      |                     ^
dna.cpp:24:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |     dif[i][j][k] = dif[i-1][j][k] + (dak[a[i]] == j && dak[b[i]] == k);
      |                                              ^
dna.cpp:24:64: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |     dif[i][j][k] = dif[i-1][j][k] + (dak[a[i]] == j && dak[b[i]] == k);
      |                                                                ^

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