# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
844392 | 2023-09-05T12:54:12 Z | 12345678 | Mutating DNA (IOI21_dna) | C++17 | 37 ms | 10320 KB |
#include "dna.h" #include <bits/stdc++.h> using namespace std; const int nx=1e5+5; int A[nx][3], B[nx][3], mp[128], ms[nx][3][3], s[3][3]; string sa, sb; int d(int v1, int v2) { return min(v1, v2); } void init(std::string a, std::string b) { mp['A']=0; mp['T']=1; mp['C']=2; for (int i=1; i<=a.size(); i++) A[i][0]=A[i-1][0], A[i][1]=A[i-1][1], A[i][2]=A[i-1][2], A[i][mp[a[i-1]]]++; for (int i=1; i<=b.size(); i++) B[i][0]=B[i-1][0], B[i][1]=B[i-1][1], B[i][2]=B[i-1][2], B[i][mp[b[i-1]]]++; for (int i=1; i<=a.size(); i++) { for (int j=0; j<3; j++) for (int k=0; k<3; k++) ms[i][j][k]=ms[i-1][j][k]; if (a[i-1]!=b[i-1]) ms[i][mp[a[i-1]]][mp[b[i-1]]]++; } sa=a; sb=b; } int get_distance(int x, int y) { x++; y++; int cnt=0, ans=0; bool can=1; for (int i=0; i<3; i++) if (A[y][i]-A[x-1][i]!=B[y][i]-B[x-1][i]) can=0; if (!can) return -1; for (int i=0; i<3; i++) for (int j=0; j<3; j++) cnt+=ms[y][i][j]-ms[x-1][i][j], s[i][j]=ms[y][i][j]-ms[x-1][i][j]; /* for (int i=0; i<3; i++) { for (int j=0; j<3; j++) cout<<s[i][j]<<' '; cout<<'\n'; }*/ int vl=d(s[1][0], s[0][1]); ans+=vl; cnt-=2*vl; vl=d(s[1][2], s[2][1]); ans+=vl; cnt-=2*vl; vl=d(s[0][2], s[2][0]); ans+=vl; cnt-=2*vl; return ans+2*cnt/3; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 8280 KB | Output is correct |
2 | Correct | 28 ms | 8280 KB | Output is correct |
3 | Correct | 25 ms | 8024 KB | Output is correct |
4 | Correct | 28 ms | 8280 KB | Output is correct |
5 | Correct | 1 ms | 2392 KB | Output is correct |
6 | Correct | 1 ms | 2392 KB | Output is correct |
7 | Correct | 1 ms | 2392 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2392 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 5 ms | 7000 KB | Output is correct |
5 | Correct | 5 ms | 7000 KB | Output is correct |
6 | Correct | 4 ms | 7000 KB | Output is correct |
7 | Correct | 5 ms | 6744 KB | Output is correct |
8 | Correct | 4 ms | 7000 KB | Output is correct |
9 | Correct | 3 ms | 7000 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2392 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 5 ms | 7000 KB | Output is correct |
5 | Correct | 5 ms | 7000 KB | Output is correct |
6 | Correct | 4 ms | 7000 KB | Output is correct |
7 | Correct | 5 ms | 6744 KB | Output is correct |
8 | Correct | 4 ms | 7000 KB | Output is correct |
9 | Correct | 3 ms | 7000 KB | Output is correct |
10 | Correct | 28 ms | 8280 KB | Output is correct |
11 | Correct | 37 ms | 8276 KB | Output is correct |
12 | Correct | 27 ms | 8536 KB | Output is correct |
13 | Correct | 27 ms | 8528 KB | Output is correct |
14 | Correct | 27 ms | 8788 KB | Output is correct |
15 | Correct | 27 ms | 8536 KB | Output is correct |
16 | Correct | 27 ms | 8532 KB | Output is correct |
17 | Correct | 27 ms | 8528 KB | Output is correct |
18 | Correct | 28 ms | 8784 KB | Output is correct |
19 | Correct | 26 ms | 8536 KB | Output is correct |
20 | Correct | 25 ms | 8528 KB | Output is correct |
21 | Correct | 26 ms | 8792 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 2392 KB | Output is correct |
2 | Correct | 1 ms | 2392 KB | Output is correct |
3 | Correct | 1 ms | 2396 KB | Output is correct |
4 | Correct | 5 ms | 7000 KB | Output is correct |
5 | Correct | 5 ms | 7000 KB | Output is correct |
6 | Correct | 4 ms | 7000 KB | Output is correct |
7 | Correct | 5 ms | 6744 KB | Output is correct |
8 | Correct | 4 ms | 7000 KB | Output is correct |
9 | Correct | 3 ms | 7000 KB | Output is correct |
10 | Correct | 3 ms | 6744 KB | Output is correct |
11 | Correct | 4 ms | 7256 KB | Output is correct |
12 | Correct | 3 ms | 7000 KB | Output is correct |
13 | Correct | 3 ms | 7256 KB | Output is correct |
14 | Correct | 4 ms | 7256 KB | Output is correct |
15 | Correct | 4 ms | 7256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 8280 KB | Output is correct |
2 | Correct | 28 ms | 8280 KB | Output is correct |
3 | Correct | 25 ms | 8024 KB | Output is correct |
4 | Correct | 28 ms | 8280 KB | Output is correct |
5 | Correct | 1 ms | 2392 KB | Output is correct |
6 | Correct | 1 ms | 2392 KB | Output is correct |
7 | Correct | 1 ms | 2392 KB | Output is correct |
8 | Correct | 1 ms | 2392 KB | Output is correct |
9 | Correct | 1 ms | 2392 KB | Output is correct |
10 | Correct | 1 ms | 2396 KB | Output is correct |
11 | Correct | 5 ms | 7000 KB | Output is correct |
12 | Correct | 5 ms | 7000 KB | Output is correct |
13 | Correct | 4 ms | 7000 KB | Output is correct |
14 | Correct | 5 ms | 6744 KB | Output is correct |
15 | Correct | 4 ms | 7000 KB | Output is correct |
16 | Correct | 3 ms | 7000 KB | Output is correct |
17 | Correct | 28 ms | 8280 KB | Output is correct |
18 | Correct | 37 ms | 8276 KB | Output is correct |
19 | Correct | 27 ms | 8536 KB | Output is correct |
20 | Correct | 27 ms | 8528 KB | Output is correct |
21 | Correct | 27 ms | 8788 KB | Output is correct |
22 | Correct | 27 ms | 8536 KB | Output is correct |
23 | Correct | 27 ms | 8532 KB | Output is correct |
24 | Correct | 27 ms | 8528 KB | Output is correct |
25 | Correct | 28 ms | 8784 KB | Output is correct |
26 | Correct | 26 ms | 8536 KB | Output is correct |
27 | Correct | 25 ms | 8528 KB | Output is correct |
28 | Correct | 26 ms | 8792 KB | Output is correct |
29 | Correct | 3 ms | 6744 KB | Output is correct |
30 | Correct | 4 ms | 7256 KB | Output is correct |
31 | Correct | 3 ms | 7000 KB | Output is correct |
32 | Correct | 3 ms | 7256 KB | Output is correct |
33 | Correct | 4 ms | 7256 KB | Output is correct |
34 | Correct | 4 ms | 7256 KB | Output is correct |
35 | Correct | 1 ms | 2648 KB | Output is correct |
36 | Correct | 26 ms | 9412 KB | Output is correct |
37 | Correct | 27 ms | 9820 KB | Output is correct |
38 | Correct | 31 ms | 9944 KB | Output is correct |
39 | Correct | 28 ms | 10160 KB | Output is correct |
40 | Correct | 28 ms | 10320 KB | Output is correct |
41 | Correct | 4 ms | 7256 KB | Output is correct |
42 | Correct | 27 ms | 10008 KB | Output is correct |
43 | Correct | 27 ms | 10076 KB | Output is correct |
44 | Correct | 29 ms | 10064 KB | Output is correct |
45 | Correct | 26 ms | 9688 KB | Output is correct |
46 | Correct | 26 ms | 10064 KB | Output is correct |
47 | Correct | 26 ms | 9856 KB | Output is correct |