# | Submission time^{} |
Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|

712500 | 2023-03-18T22:37:19 Z | Kripton | Mutating DNA (IOI21_dna) | C++17 | 51 ms | 8648 KB |

#include <bits/stdc++.h> #include "dna.h" using namespace std; int a1[100001], a2[100001]; int c1[100001], c2[100001]; int t1[100001], t2[100001]; int difat[100001], difta[100001]; int difac[100001], difca[100001]; int diftc[100001], difct[100001]; void init(string a, string b) { for(int i = 1; i <= a.size(); i++) { c1[i] = c1[i - 1] + (a[i - 1] == 'C'); a1[i] = a1[i - 1] + (a[i - 1] == 'A'); t1[i] = t1[i - 1] + (a[i - 1] == 'T'); c2[i] = c2[i - 1] + (b[i - 1] == 'C'); a2[i] = a2[i - 1] + (b[i - 1] == 'A'); t2[i] = t2[i - 1] + (b[i - 1] == 'T'); difat[i] = difat[i - 1] + (a[i - 1] == 'A' && b[i - 1] == 'T'); difta[i] = difta[i - 1] + (a[i - 1] == 'T' && b[i - 1] == 'A'); difac[i] = difac[i - 1] + (a[i - 1] == 'A' && b[i - 1] == 'C'); difca[i] = difca[i - 1] + (a[i - 1] == 'C' && b[i - 1] == 'A'); difct[i] = difct[i - 1] + (a[i - 1] == 'C' && b[i - 1] == 'T'); diftc[i] = diftc[i - 1] + (a[i - 1] == 'T' && b[i - 1] == 'C'); } } int get_distance(int x, int y) { x++; y++; if(c1[y] - c1[x - 1] != c2[y] - c2[x - 1]) return -1; if(a1[y] - a1[x - 1] != a2[y] - a2[x - 1]) return -1; if(t1[y] - t1[x - 1] != t2[y] - t2[x - 1]) return -1; int rez = 0, mini; int at = difat[y] - difat[x - 1], ta = difta[y] - difta[x - 1]; mini = min(at, ta); rez += mini; at -= mini; ta -= mini; int ac = difac[y] - difac[x - 1], ca = difca[y] - difca[x - 1]; mini = min(ac, ca); rez += mini; ac -= mini; ca -= mini; int tc = diftc[y] - diftc[x - 1], ct = difct[y] - difct[x - 1]; mini = min(tc, ct); rez += mini; tc -= mini; ct -= mini; return rez + (at + ta + ac + ca + tc + ct) / 3 * 2; }

### Compilation message

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 51 ms | 6792 KB | Output is correct |

2 | Correct | 33 ms | 6796 KB | Output is correct |

3 | Correct | 33 ms | 6428 KB | Output is correct |

4 | Correct | 38 ms | 6792 KB | Output is correct |

5 | Correct | 1 ms | 340 KB | Output is correct |

6 | Correct | 1 ms | 340 KB | Output is correct |

7 | Correct | 0 ms | 340 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 340 KB | Output is correct |

2 | Correct | 1 ms | 340 KB | Output is correct |

3 | Correct | 1 ms | 340 KB | Output is correct |

4 | Correct | 5 ms | 5460 KB | Output is correct |

5 | Correct | 5 ms | 5460 KB | Output is correct |

6 | Correct | 5 ms | 5460 KB | Output is correct |

7 | Correct | 5 ms | 5204 KB | Output is correct |

8 | Correct | 5 ms | 5460 KB | Output is correct |

9 | Correct | 5 ms | 5460 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 340 KB | Output is correct |

2 | Correct | 1 ms | 340 KB | Output is correct |

3 | Correct | 1 ms | 340 KB | Output is correct |

4 | Correct | 5 ms | 5460 KB | Output is correct |

5 | Correct | 5 ms | 5460 KB | Output is correct |

6 | Correct | 5 ms | 5460 KB | Output is correct |

7 | Correct | 5 ms | 5204 KB | Output is correct |

8 | Correct | 5 ms | 5460 KB | Output is correct |

9 | Correct | 5 ms | 5460 KB | Output is correct |

10 | Correct | 36 ms | 6796 KB | Output is correct |

11 | Correct | 50 ms | 6776 KB | Output is correct |

12 | Correct | 31 ms | 6800 KB | Output is correct |

13 | Correct | 31 ms | 6940 KB | Output is correct |

14 | Correct | 33 ms | 7172 KB | Output is correct |

15 | Correct | 34 ms | 7168 KB | Output is correct |

16 | Correct | 37 ms | 6900 KB | Output is correct |

17 | Correct | 33 ms | 7008 KB | Output is correct |

18 | Correct | 30 ms | 7176 KB | Output is correct |

19 | Correct | 28 ms | 6920 KB | Output is correct |

20 | Correct | 30 ms | 7096 KB | Output is correct |

21 | Correct | 32 ms | 7188 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 1 ms | 340 KB | Output is correct |

2 | Correct | 1 ms | 340 KB | Output is correct |

3 | Correct | 1 ms | 340 KB | Output is correct |

4 | Correct | 5 ms | 5460 KB | Output is correct |

5 | Correct | 5 ms | 5460 KB | Output is correct |

6 | Correct | 5 ms | 5460 KB | Output is correct |

7 | Correct | 5 ms | 5204 KB | Output is correct |

8 | Correct | 5 ms | 5460 KB | Output is correct |

9 | Correct | 5 ms | 5460 KB | Output is correct |

10 | Correct | 5 ms | 5076 KB | Output is correct |

11 | Correct | 5 ms | 5520 KB | Output is correct |

12 | Correct | 4 ms | 5204 KB | Output is correct |

13 | Correct | 5 ms | 5716 KB | Output is correct |

14 | Correct | 5 ms | 5716 KB | Output is correct |

15 | Correct | 5 ms | 5716 KB | Output is correct |

# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|

1 | Correct | 51 ms | 6792 KB | Output is correct |

2 | Correct | 33 ms | 6796 KB | Output is correct |

3 | Correct | 33 ms | 6428 KB | Output is correct |

4 | Correct | 38 ms | 6792 KB | Output is correct |

5 | Correct | 1 ms | 340 KB | Output is correct |

6 | Correct | 1 ms | 340 KB | Output is correct |

7 | Correct | 0 ms | 340 KB | Output is correct |

8 | Correct | 1 ms | 340 KB | Output is correct |

9 | Correct | 1 ms | 340 KB | Output is correct |

10 | Correct | 1 ms | 340 KB | Output is correct |

11 | Correct | 5 ms | 5460 KB | Output is correct |

12 | Correct | 5 ms | 5460 KB | Output is correct |

13 | Correct | 5 ms | 5460 KB | Output is correct |

14 | Correct | 5 ms | 5204 KB | Output is correct |

15 | Correct | 5 ms | 5460 KB | Output is correct |

16 | Correct | 5 ms | 5460 KB | Output is correct |

17 | Correct | 36 ms | 6796 KB | Output is correct |

18 | Correct | 50 ms | 6776 KB | Output is correct |

19 | Correct | 31 ms | 6800 KB | Output is correct |

20 | Correct | 31 ms | 6940 KB | Output is correct |

21 | Correct | 33 ms | 7172 KB | Output is correct |

22 | Correct | 34 ms | 7168 KB | Output is correct |

23 | Correct | 37 ms | 6900 KB | Output is correct |

24 | Correct | 33 ms | 7008 KB | Output is correct |

25 | Correct | 30 ms | 7176 KB | Output is correct |

26 | Correct | 28 ms | 6920 KB | Output is correct |

27 | Correct | 30 ms | 7096 KB | Output is correct |

28 | Correct | 32 ms | 7188 KB | Output is correct |

29 | Correct | 5 ms | 5076 KB | Output is correct |

30 | Correct | 5 ms | 5520 KB | Output is correct |

31 | Correct | 4 ms | 5204 KB | Output is correct |

32 | Correct | 5 ms | 5716 KB | Output is correct |

33 | Correct | 5 ms | 5716 KB | Output is correct |

34 | Correct | 5 ms | 5716 KB | Output is correct |

35 | Correct | 1 ms | 340 KB | Output is correct |

36 | Correct | 36 ms | 7780 KB | Output is correct |

37 | Correct | 37 ms | 8180 KB | Output is correct |

38 | Correct | 36 ms | 8212 KB | Output is correct |

39 | Correct | 40 ms | 8576 KB | Output is correct |

40 | Correct | 36 ms | 8564 KB | Output is correct |

41 | Correct | 5 ms | 5716 KB | Output is correct |

42 | Correct | 32 ms | 8184 KB | Output is correct |

43 | Correct | 31 ms | 8444 KB | Output is correct |

44 | Correct | 39 ms | 8648 KB | Output is correct |

45 | Correct | 30 ms | 8172 KB | Output is correct |

46 | Correct | 41 ms | 8452 KB | Output is correct |

47 | Correct | 30 ms | 8476 KB | Output is correct |