Submission #914657

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
914657	2024-01-22 13:26:59	JooDdae	Mutating DNA (IOI21_dna)	C++17	100 / 100	42 ms	7488 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;
using ll = long long;
int r[256], n, s[100100][3][3], c[3][3], p[3];
void init(string a, string b) {
    r['A'] = 0, r['T'] = 1, r['C'] = 2;
    n = a.size();
    for(int i=0;i<n;i++) {
        int A = r[a[i]], B = r[b[i]];
        for(int j=0;j<3;j++) for(int k=0;k<3;k++) s[i+1][j][k] = s[i][j][k] + (j == A && k == B);
    }
}
int get_distance(int x, int y) {
    for(int i=0;i<3;i++) for(int j=0;j<3;j++) c[i][j] = s[y+1][i][j] - s[x][i][j];
    p[0] = p[1] = p[2] = 0;
    for(int i=0;i<3;i++) for(int j=0;j<3;j++) p[i] += c[i][j], p[j] -= c[i][j];
    if(p[0] || p[1] || p[2]) return -1;
    int ans = 0;
    for(int i=0;i<3;i++) for(int j=i+1;j<3;j++) {
        int k = min(c[i][j], c[j][i]);
        ans += k, c[i][j] -= k, c[j][i] -= k;
    }
    return ans + c[0][1]*2 + c[1][0]*2;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:13:23: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |         int A = r[a[i]], B = r[b[i]];
      |                       ^
dna.cpp:13:36: warning: array subscript has type 'char' [-Wchar-subscripts]
   13 |         int A = r[a[i]], B = r[b[i]];
      |                                    ^

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