# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
792006 | 2023-07-24T13:44:04 Z | Karpin | Mutating DNA (IOI21_dna) | C++17 | 49 ms | 8780 KB |
#include "dna.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define vt vector vt<int> aamountofA; vt<int> aamountofT; vt<int> aamountofC; vt<int> bamountofA; vt<int> bamountofT; vt<int> bamountofC; vt<int>amountofAT; vt<int>amountofAC; vt<int>amountofTA; vt<int>amountofTC; vt<int>amountofCA; vt<int>amountofCT; void init(std::string a, std::string b) { for(int i = 0; i < a.length(); i++){ aamountofA.push_back(0); aamountofT.push_back(0); aamountofC.push_back(0); bamountofA.push_back(0); bamountofT.push_back(0); bamountofC.push_back(0); amountofAT.push_back(0); amountofAC.push_back(0); amountofTA.push_back(0); amountofTC.push_back(0); amountofCA.push_back(0); amountofCT.push_back(0); } if (a[0] == 'A') aamountofA[0] = 1; if (a[0] == 'T') aamountofT[0] = 1; if (a[0] == 'C') aamountofC[0] = 1; if (b[0] == 'A') bamountofA[0] = 1; if (b[0] == 'T') bamountofT[0] = 1; if (b[0] == 'C') bamountofC[0] = 1; if (a[0] == 'A' && b[0] == 'T') amountofAT[0] = 1; if (a[0] == 'A' && b[0] == 'C') amountofAC[0] = 1; if (a[0] == 'T' && b[0] == 'A') amountofTA[0] = 1; if (a[0] == 'T' && b[0] == 'C') amountofTC[0] = 1; if (a[0] == 'C' && b[0] == 'A') amountofCA[0] = 1; if (a[0] == 'C' && b[0] == 'T') amountofCT[0] = 1; for(int i = 1; i < a.length(); i++){ aamountofA[i] = aamountofA[i - 1]; aamountofC[i] = aamountofC[i - 1]; aamountofT[i] = aamountofT[i - 1]; bamountofA[i] = bamountofA[i - 1]; bamountofC[i] = bamountofC[i - 1]; bamountofT[i] = bamountofT[i - 1]; amountofAT[i] = amountofAT[i - 1]; amountofAC[i] = amountofAC[i - 1]; amountofTA[i] = amountofTA[i - 1]; amountofTC[i] = amountofTC[i - 1]; amountofCA[i] = amountofCA[i - 1]; amountofCT[i] = amountofCT[i - 1]; if(a[i] == 'A') aamountofA[i] = aamountofA[i - 1] + 1; if(a[i] == 'T') aamountofT[i] = aamountofT[i - 1] + 1; if(a[i] == 'C') aamountofC[i] = aamountofC[i - 1] + 1; if(b[i] == 'A') bamountofA[i] = bamountofA[i - 1] + 1; if(b[i] == 'T') bamountofT[i] = bamountofT[i - 1] + 1; if(b[i] == 'C') bamountofC[i] = bamountofC[i - 1] + 1; if (a[i] == 'A' && b[i] == 'T') amountofAT[i] = amountofAT[i - 1] + 1; if (a[i] == 'A' && b[i] == 'C') amountofAC[i] = amountofAC[i - 1] + 1; if (a[i] == 'T' && b[i] == 'A') amountofTA[i] = amountofTA[i - 1] + 1; if (a[i] == 'T' && b[i] == 'C') amountofTC[i] = amountofTC[i - 1] + 1; if (a[i] == 'C' && b[i] == 'A') amountofCA[i] = amountofCA[i - 1] + 1; if (a[i] == 'C' && b[i] == 'T') amountofCT[i] = amountofCT[i - 1] + 1; } } int get_distance(int x, int y) { int firstamountofA = aamountofA[y]; int firstamountofC = aamountofC[y]; int firstamountofT = aamountofT[y]; int secamountofA = bamountofA[y]; int secamountofC = bamountofC[y]; int secamountofT = bamountofT[y]; int amofAT = amountofAT[y]; int amofAC = amountofAC[y]; int amofTA = amountofTA[y]; int amofTC = amountofTC[y]; int amofCA = amountofCA[y]; int amofCT = amountofCT[y]; if(x > 0){ firstamountofA -= aamountofA[x - 1]; firstamountofC -= aamountofC[x - 1]; firstamountofT -= aamountofT[x - 1]; secamountofC -= bamountofC[x - 1]; secamountofT -= bamountofT[x - 1]; secamountofA -= bamountofA[x - 1]; amofAT -= amountofAT[x - 1]; amofAC -= amountofAC[x - 1]; amofTA -= amountofTA[x - 1]; amofTC -= amountofTC[x - 1]; amofCA -= amountofCA[x - 1]; amofCT -= amountofCT[x - 1]; } if (firstamountofA != secamountofA) return -1; if (firstamountofT != secamountofT) return -1; if (firstamountofC != secamountofC) return -1; ll res = 0; res += min(amofAT, amofTA); res += min(amofAC, amofCA); res += min(amofTC, amofCT); int realamofAT = max(0, amofAT - amofTA); int realamofTA = max(0, amofTA - amofAT); int realamofAC = max(0, amofAC - amofCA); int realamofCA = max(0, amofCA - amofAC); int realamofTC = max(0, amofTC - amofCT); int realamofCT = max(0, amofCT - amofTC); res += 2 * (realamofAC + realamofCA); return res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 8332 KB | Output is correct |
2 | Correct | 42 ms | 8432 KB | Output is correct |
3 | Correct | 40 ms | 7924 KB | Output is correct |
4 | Correct | 43 ms | 8356 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 16 ms | 5884 KB | Output is correct |
5 | Correct | 17 ms | 5908 KB | Output is correct |
6 | Correct | 17 ms | 5912 KB | Output is correct |
7 | Correct | 15 ms | 5576 KB | Output is correct |
8 | Correct | 16 ms | 5964 KB | Output is correct |
9 | Correct | 18 ms | 5880 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 16 ms | 5884 KB | Output is correct |
5 | Correct | 17 ms | 5908 KB | Output is correct |
6 | Correct | 17 ms | 5912 KB | Output is correct |
7 | Correct | 15 ms | 5576 KB | Output is correct |
8 | Correct | 16 ms | 5964 KB | Output is correct |
9 | Correct | 18 ms | 5880 KB | Output is correct |
10 | Correct | 44 ms | 8512 KB | Output is correct |
11 | Correct | 41 ms | 8428 KB | Output is correct |
12 | Correct | 42 ms | 8272 KB | Output is correct |
13 | Correct | 42 ms | 8460 KB | Output is correct |
14 | Correct | 43 ms | 8780 KB | Output is correct |
15 | Correct | 42 ms | 8640 KB | Output is correct |
16 | Correct | 49 ms | 8280 KB | Output is correct |
17 | Correct | 42 ms | 8396 KB | Output is correct |
18 | Correct | 42 ms | 8676 KB | Output is correct |
19 | Correct | 40 ms | 8264 KB | Output is correct |
20 | Correct | 40 ms | 8412 KB | Output is correct |
21 | Correct | 41 ms | 8664 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 212 KB | Output is correct |
4 | Correct | 16 ms | 5884 KB | Output is correct |
5 | Correct | 17 ms | 5908 KB | Output is correct |
6 | Correct | 17 ms | 5912 KB | Output is correct |
7 | Correct | 15 ms | 5576 KB | Output is correct |
8 | Correct | 16 ms | 5964 KB | Output is correct |
9 | Correct | 18 ms | 5880 KB | Output is correct |
10 | Correct | 15 ms | 5392 KB | Output is correct |
11 | Correct | 18 ms | 5908 KB | Output is correct |
12 | Correct | 15 ms | 5620 KB | Output is correct |
13 | Correct | 16 ms | 5856 KB | Output is correct |
14 | Correct | 16 ms | 5972 KB | Output is correct |
15 | Correct | 17 ms | 5968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 41 ms | 8332 KB | Output is correct |
2 | Correct | 42 ms | 8432 KB | Output is correct |
3 | Correct | 40 ms | 7924 KB | Output is correct |
4 | Correct | 43 ms | 8356 KB | Output is correct |
5 | Correct | 0 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 212 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 1 ms | 212 KB | Output is correct |
10 | Correct | 0 ms | 212 KB | Output is correct |
11 | Correct | 16 ms | 5884 KB | Output is correct |
12 | Correct | 17 ms | 5908 KB | Output is correct |
13 | Correct | 17 ms | 5912 KB | Output is correct |
14 | Correct | 15 ms | 5576 KB | Output is correct |
15 | Correct | 16 ms | 5964 KB | Output is correct |
16 | Correct | 18 ms | 5880 KB | Output is correct |
17 | Correct | 44 ms | 8512 KB | Output is correct |
18 | Correct | 41 ms | 8428 KB | Output is correct |
19 | Correct | 42 ms | 8272 KB | Output is correct |
20 | Correct | 42 ms | 8460 KB | Output is correct |
21 | Correct | 43 ms | 8780 KB | Output is correct |
22 | Correct | 42 ms | 8640 KB | Output is correct |
23 | Correct | 49 ms | 8280 KB | Output is correct |
24 | Correct | 42 ms | 8396 KB | Output is correct |
25 | Correct | 42 ms | 8676 KB | Output is correct |
26 | Correct | 40 ms | 8264 KB | Output is correct |
27 | Correct | 40 ms | 8412 KB | Output is correct |
28 | Correct | 41 ms | 8664 KB | Output is correct |
29 | Correct | 15 ms | 5392 KB | Output is correct |
30 | Correct | 18 ms | 5908 KB | Output is correct |
31 | Correct | 15 ms | 5620 KB | Output is correct |
32 | Correct | 16 ms | 5856 KB | Output is correct |
33 | Correct | 16 ms | 5972 KB | Output is correct |
34 | Correct | 17 ms | 5968 KB | Output is correct |
35 | Correct | 0 ms | 212 KB | Output is correct |
36 | Correct | 40 ms | 7948 KB | Output is correct |
37 | Correct | 41 ms | 8440 KB | Output is correct |
38 | Correct | 41 ms | 8436 KB | Output is correct |
39 | Correct | 44 ms | 8772 KB | Output is correct |
40 | Correct | 46 ms | 8724 KB | Output is correct |
41 | Correct | 16 ms | 5964 KB | Output is correct |
42 | Correct | 41 ms | 8364 KB | Output is correct |
43 | Correct | 43 ms | 8672 KB | Output is correct |
44 | Correct | 45 ms | 8684 KB | Output is correct |
45 | Correct | 40 ms | 8332 KB | Output is correct |
46 | Correct | 43 ms | 8712 KB | Output is correct |
47 | Correct | 41 ms | 8656 KB | Output is correct |