# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
739884 |
2023-05-11T14:00:04 Z |
abczz |
Mutating DNA (IOI21_dna) |
C++17 |
|
107 ms |
16432 KB |
#include <iostream>
#include <array>
#include "dna.h"
#define ll long long
using namespace std;
array<ll, 6> st[400000], Q;
string S, T, D[6] = {"AT", "AC", "TC", "CT", "CA", "TA"};
ll n, f, z, C[26], R[6], mx;
void build(ll id, ll l, ll r) {
if (l == r) {
for (int i=0; i<6; ++i) {
if (D[i][0] == S[l] && D[i][1] == T[l]) {
++st[id][i];
break;
}
}
return;
}
ll mid = (l+r)/2, z;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = st[id*2];
for (int i=0; i<6; ++i) {
st[id][i] += st[id*2+1][i];
}
}
void query(ll id, ll l, ll r, ll ql, ll qr) {
if (r < ql || qr < l) return;
else if (ql <= l && r <= qr) {
for (int i=0; i<6; ++i) {
Q[i] += st[id][i];
}
return;
}
ll mid = (l+r)/2;
query(id*2, l, mid, ql, qr);
query(id*2+1, mid+1, r, ql, qr);
}
void init(std::string a, std::string b) {
S = a, T = b;
n = a.size();
C['A'-'A'] = 0, C['T'-'A'] = 1, C['C'-'A'] = 2;
build(1, 0, n-1);
}
int get_distance(int x, int y) {
for (int i=0; i<6; ++i) R[i] = Q[i] = 0;
f = mx = 0;
query(1, 0, n-1, x, y);
for (int i=0; i<3; ++i) {
z = min(Q[i], Q[5-i]);
Q[i] -= z, Q[5-i] -= z;
f += z;
}
for (int i=0; i<6; ++i) {
mx = max(mx, Q[i]);
for (int j=0; j<2; ++j) {
R[C[D[i][j]-'A']+j*3] += Q[i];
}
}
for (int i=0; i<3; ++i) {
if (R[i] != R[i+3]) return -1;
}
return f+mx*2;
}
Compilation message
dna.cpp: In function 'void build(long long int, long long int, long long int)':
dna.cpp:22:20: warning: unused variable 'z' [-Wunused-variable]
22 | ll mid = (l+r)/2, z;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
15012 KB |
Output is correct |
2 |
Correct |
60 ms |
15056 KB |
Output is correct |
3 |
Correct |
61 ms |
14868 KB |
Output is correct |
4 |
Correct |
61 ms |
16052 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
304 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
9 ms |
13576 KB |
Output is correct |
5 |
Correct |
11 ms |
13524 KB |
Output is correct |
6 |
Correct |
9 ms |
13524 KB |
Output is correct |
7 |
Correct |
9 ms |
13524 KB |
Output is correct |
8 |
Correct |
13 ms |
13524 KB |
Output is correct |
9 |
Correct |
9 ms |
13500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
9 ms |
13576 KB |
Output is correct |
5 |
Correct |
11 ms |
13524 KB |
Output is correct |
6 |
Correct |
9 ms |
13524 KB |
Output is correct |
7 |
Correct |
9 ms |
13524 KB |
Output is correct |
8 |
Correct |
13 ms |
13524 KB |
Output is correct |
9 |
Correct |
9 ms |
13500 KB |
Output is correct |
10 |
Correct |
75 ms |
14936 KB |
Output is correct |
11 |
Correct |
75 ms |
15008 KB |
Output is correct |
12 |
Correct |
93 ms |
15264 KB |
Output is correct |
13 |
Correct |
89 ms |
15264 KB |
Output is correct |
14 |
Correct |
84 ms |
15340 KB |
Output is correct |
15 |
Correct |
86 ms |
15272 KB |
Output is correct |
16 |
Correct |
78 ms |
15272 KB |
Output is correct |
17 |
Correct |
77 ms |
15424 KB |
Output is correct |
18 |
Correct |
81 ms |
15472 KB |
Output is correct |
19 |
Correct |
67 ms |
15604 KB |
Output is correct |
20 |
Correct |
68 ms |
15620 KB |
Output is correct |
21 |
Correct |
70 ms |
15596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
304 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
9 ms |
13576 KB |
Output is correct |
5 |
Correct |
11 ms |
13524 KB |
Output is correct |
6 |
Correct |
9 ms |
13524 KB |
Output is correct |
7 |
Correct |
9 ms |
13524 KB |
Output is correct |
8 |
Correct |
13 ms |
13524 KB |
Output is correct |
9 |
Correct |
9 ms |
13500 KB |
Output is correct |
10 |
Correct |
9 ms |
13504 KB |
Output is correct |
11 |
Correct |
10 ms |
13500 KB |
Output is correct |
12 |
Correct |
10 ms |
13500 KB |
Output is correct |
13 |
Correct |
12 ms |
13520 KB |
Output is correct |
14 |
Correct |
10 ms |
13504 KB |
Output is correct |
15 |
Correct |
11 ms |
13504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
15012 KB |
Output is correct |
2 |
Correct |
60 ms |
15056 KB |
Output is correct |
3 |
Correct |
61 ms |
14868 KB |
Output is correct |
4 |
Correct |
61 ms |
16052 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
304 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
304 KB |
Output is correct |
10 |
Correct |
1 ms |
308 KB |
Output is correct |
11 |
Correct |
9 ms |
13576 KB |
Output is correct |
12 |
Correct |
11 ms |
13524 KB |
Output is correct |
13 |
Correct |
9 ms |
13524 KB |
Output is correct |
14 |
Correct |
9 ms |
13524 KB |
Output is correct |
15 |
Correct |
13 ms |
13524 KB |
Output is correct |
16 |
Correct |
9 ms |
13500 KB |
Output is correct |
17 |
Correct |
75 ms |
14936 KB |
Output is correct |
18 |
Correct |
75 ms |
15008 KB |
Output is correct |
19 |
Correct |
93 ms |
15264 KB |
Output is correct |
20 |
Correct |
89 ms |
15264 KB |
Output is correct |
21 |
Correct |
84 ms |
15340 KB |
Output is correct |
22 |
Correct |
86 ms |
15272 KB |
Output is correct |
23 |
Correct |
78 ms |
15272 KB |
Output is correct |
24 |
Correct |
77 ms |
15424 KB |
Output is correct |
25 |
Correct |
81 ms |
15472 KB |
Output is correct |
26 |
Correct |
67 ms |
15604 KB |
Output is correct |
27 |
Correct |
68 ms |
15620 KB |
Output is correct |
28 |
Correct |
70 ms |
15596 KB |
Output is correct |
29 |
Correct |
9 ms |
13504 KB |
Output is correct |
30 |
Correct |
10 ms |
13500 KB |
Output is correct |
31 |
Correct |
10 ms |
13500 KB |
Output is correct |
32 |
Correct |
12 ms |
13520 KB |
Output is correct |
33 |
Correct |
10 ms |
13504 KB |
Output is correct |
34 |
Correct |
11 ms |
13504 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
71 ms |
15936 KB |
Output is correct |
37 |
Correct |
72 ms |
16108 KB |
Output is correct |
38 |
Correct |
96 ms |
16356 KB |
Output is correct |
39 |
Correct |
102 ms |
16428 KB |
Output is correct |
40 |
Correct |
107 ms |
16432 KB |
Output is correct |
41 |
Correct |
10 ms |
13524 KB |
Output is correct |
42 |
Correct |
89 ms |
16284 KB |
Output is correct |
43 |
Correct |
106 ms |
16332 KB |
Output is correct |
44 |
Correct |
79 ms |
16340 KB |
Output is correct |
45 |
Correct |
72 ms |
16268 KB |
Output is correct |
46 |
Correct |
68 ms |
16324 KB |
Output is correct |
47 |
Correct |
67 ms |
16320 KB |
Output is correct |