Submission #565169

#	Time	Username	Problem	Language	Result	Execution time	Memory
565169		hoanghq2004	Mutating DNA (IOI21_dna)	C++17	100 / 100	51 ms	6072 KiB

dna

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "dna.h"

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 1e5 + 10;

int code[256];
int s[N][3][3];

void init(string a, string b) {
    code['A'] = 0, code['C'] = 1, code['T'] = 2;
    int n = a.size();
    for (int i = 1; i <= n; ++i) {
        for (int x = 0; x < 3; ++x)
            for (int y = 0; y < 3; ++y)
                s[i][x][y] = s[i - 1][x][y];
        ++s[i][code[a[i - 1]]][code[b[i - 1]]];
    }
}

int get_distance(int L, int R) {
    ++L, ++R;
    int need = 0;
    int rem = 0;
    for (int x = 0; x < 3; ++x) {
        int num = 0;
        for (int y = 0; y < 3; ++y)
            num += s[R][x][y] - s[L - 1][x][y];
        for (int y = 0; y < 3; ++y)
            num -= s[R][y][x] - s[L - 1][y][x];
        if (num) return -1;
    }
    for (int x = 0; x < 3; ++x) {
        for (int y = x + 1; y < 3; ++y) {
            need += min(s[R][x][y] - s[L - 1][x][y], s[R][y][x] - s[L - 1][y][x]);
            rem += max(s[R][x][y] - s[L - 1][x][y], s[R][y][x] - s[L - 1][y][x]) - min(s[R][x][y] - s[L - 1][x][y], s[R][y][x] - s[L - 1][y][x]);
        }
    }
    need += rem * 2 / 3;
    return need;
}

//
//int main() {
//	int n, q;
//	assert(scanf("%d %d", &n, &q) == 2);
//	char A[n+1], B[n+1];
//	assert(scanf("%s", A) == 1);
//	assert(scanf("%s", B) == 1);
//	std::string a = std::string(A);
//	std::string b = std::string(B);
//	std::vector<int> x(q), y(q);
//	for (int i = 0; i < q; i++) {
//		assert(scanf("%d %d", &x[i], &y[i]) == 2);
//	}
//	fclose(stdin);
//	std::vector<int> results(q);
//	init(a, b);
//	for (int i = 0; i < q; i++) {
//		results[i] = get_distance(x[i], y[i]);
//	}
//	for (int i = 0; i < q; i++) {
//		printf("%d\n", results[i]);
//	}
//	fclose(stdout);
//	return 0;
//}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:26:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         ++s[i][code[a[i - 1]]][code[b[i - 1]]];
      |                             ^
dna.cpp:26:45: warning: array subscript has type 'char' [-Wchar-subscripts]
   26 |         ++s[i][code[a[i - 1]]][code[b[i - 1]]];
      |                                             ^

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