Submission #437025

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
437025	2021-06-25 16:07:12	model_code	Mutating DNA (IOI21_dna)	C++17	100 / 100	127 ms	7584 KiB

dna

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const string kDna = "ACT";
const int K = kDna.size();
vector<int> prefix_sum[sizeof(char) << 8][sizeof(char) << 8];
int cnt[sizeof(char) << 8][sizeof(char) << 8];
vector<string> dna_subsets;
constexpr int kImpossible = -1;
void init(string A, string B) {
  int N = A.size();
  for (int c1 : kDna) {
    for (int c2 : kDna) {
      prefix_sum[c1][c2].resize(N);
    }
  }
  for (int c1 : kDna) {
    for (int c2 : kDna) {
      for (int i = 0; i < N; ++i) {
        prefix_sum[c1][c2][i] = (c1 == A[i] && c2 == B[i]) ? 1 : 0;
        if (i > 0) {
          prefix_sum[c1][c2][i] += prefix_sum[c1][c2][i - 1];
        }
      }
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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