Submission #784098

#	Time	Username	Problem	Language	Result	Execution time	Memory
784098		zsombor	Mutating DNA (IOI21_dna)	C++17	100 / 100	38 ms	8340 KiB

dna

#include <iostream>
#include <vector>
#include "dna.h"
using namespace std;

vector <int> a(1e5, 0);
vector <int> b(1e5, 0);
vector <vector <vector <int>>> p(3, vector <vector <int>>(3, vector <int>(1e5, 0)));
vector <vector <int>> v(3, vector <int>(3, 0));

int num(char c) {
	if (c == 'A') return 0;
	if (c == 'T') return 1;
	return 2;
}

void init(string A, string B) {
	for (int k = 0; k < A.size(); k++) {
		a[k] = num(A[k]);
		b[k] = num(B[k]);
		p[a[k]][b[k]][k]++;
	}
	for (int k = 1; k < A.size(); k++) {
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				p[i][j][k] += p[i][j][k - 1];
			}
		}
	}
}

int cnt(int i, int j, int l, int r) {
	return (l ? p[i][j][r] - p[i][j][l - 1] : p[i][j][r]);
}

void get_v(int l, int r) {
	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			v[i][j] = cnt(i, j, l, r);
		}
	}
}

int get_distance(int l, int r) {
	get_v(l, r);
	int mn, ans = 0;
	for (int i = 0; i < 3; i++) {
		for (int j = i + 1; j < 3; j++) {
			mn = min(v[i][j], v[j][i]);
			v[i][j] -= mn;
			v[j][i] -= mn;
			ans += mn;
		}
	}
	if (v[0][1] != v[1][2] || v[0][1] != v[2][0]) return -1;
	if (v[1][0] != v[2][1] || v[1][0] != v[0][2]) return -1;
	ans += 2 * v[0][1];
	ans += 2 * v[1][0];
	return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:18:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (int k = 0; k < A.size(); k++) {
      |                  ~~^~~~~~~~~~
dna.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for (int k = 1; k < A.size(); k++) {
      |                  ~~^~~~~~~~~~

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