# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
439336 | 2021-06-29T16:06:27 Z | fvogel499 | Mutating DNA (IOI21_dna) | C++17 | 1500 ms | 8704 KB |
#include <bits/stdc++.h> using namespace std; const int siz = 100010; int psA [3][siz]; int psB [3][siz]; int insteadOf [3][3][siz]; int conv(char c) { if (c == 'A') return 0; else if (c == 'T') return 1; else return 2; } void init(string a, string b) { for (int i = 0; i < a.size(); i++) { for (int j = 0; j < 3; j++) { psA[j][i] = 0; psB[j][i] = 0; for (int k = 0; k < 3; k++) { insteadOf[j][k][i] = 0; } } } for (int i = 0; i < a.size(); i++) { psA[conv(a[i])][i]++; psB[conv(b[i])][i]++; insteadOf[conv(a[i])][conv(b[i])][i]++; } for (int i = 1; i < a.size(); i++) { for (int j = 0; j < 3; j++) { psA[j][i] += psA[j][i-1]; psB[j][i] += psB[j][i-1]; for (int k = 0; k < 3; k++) { insteadOf[j][k][i] += insteadOf[j][k][i-1]; } } } } int get_distance(int x, int y) { for (int i = 0; i < 3; i++) { int aSum = psA[i][y]; int bSum = psB[i][y]; if (x > 0) { aSum -= psA[i][x-1]; bSum -= psB[i][x-1]; } if (aSum != bSum) { return -1; } } int ins [3][3]; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { ins[i][j] = insteadOf[i][j][y]; if (x > 0) ins[i][j] -= insteadOf[i][j][x-1]; } } for (int i = 0; i < 3; i++) ins[i][i] = 0; int count = 0; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { while (ins[i][j] and ins[j][i]) { count++; ins[i][j]--; ins[j][i]--; } } } int cycleLeft = 0; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) cycleLeft = max(cycleLeft, ins[i][j]); count += 2*cycleLeft; return count; } // int main() { // string a, b; // cin >> a >> b; // init(a, b); // int q; // cin >> q; // for (int i = 0; i < q; i++) { // int x, y; // cin >> x >> y; // cout << get_distance(x, y) << endl; // } // int d = 0; // d++; // }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 66 ms | 7912 KB | Output is correct |
2 | Correct | 57 ms | 7940 KB | Output is correct |
3 | Correct | 56 ms | 7572 KB | Output is correct |
4 | Correct | 57 ms | 8704 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 0 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 10 ms | 6620 KB | Output is correct |
5 | Correct | 10 ms | 6732 KB | Output is correct |
6 | Correct | 10 ms | 6732 KB | Output is correct |
7 | Correct | 9 ms | 6348 KB | Output is correct |
8 | Correct | 10 ms | 6752 KB | Output is correct |
9 | Correct | 9 ms | 6732 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 10 ms | 6620 KB | Output is correct |
5 | Correct | 10 ms | 6732 KB | Output is correct |
6 | Correct | 10 ms | 6732 KB | Output is correct |
7 | Correct | 9 ms | 6348 KB | Output is correct |
8 | Correct | 10 ms | 6752 KB | Output is correct |
9 | Correct | 9 ms | 6732 KB | Output is correct |
10 | Correct | 60 ms | 8008 KB | Output is correct |
11 | Correct | 56 ms | 7932 KB | Output is correct |
12 | Execution timed out | 1577 ms | 7440 KB | Time limit exceeded |
13 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 332 KB | Output is correct |
2 | Correct | 1 ms | 332 KB | Output is correct |
3 | Correct | 1 ms | 332 KB | Output is correct |
4 | Correct | 10 ms | 6620 KB | Output is correct |
5 | Correct | 10 ms | 6732 KB | Output is correct |
6 | Correct | 10 ms | 6732 KB | Output is correct |
7 | Correct | 9 ms | 6348 KB | Output is correct |
8 | Correct | 10 ms | 6752 KB | Output is correct |
9 | Correct | 9 ms | 6732 KB | Output is correct |
10 | Correct | 9 ms | 6220 KB | Output is correct |
11 | Correct | 10 ms | 6908 KB | Output is correct |
12 | Correct | 10 ms | 6556 KB | Output is correct |
13 | Correct | 11 ms | 6860 KB | Output is correct |
14 | Correct | 10 ms | 6860 KB | Output is correct |
15 | Correct | 9 ms | 6944 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 66 ms | 7912 KB | Output is correct |
2 | Correct | 57 ms | 7940 KB | Output is correct |
3 | Correct | 56 ms | 7572 KB | Output is correct |
4 | Correct | 57 ms | 8704 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 0 ms | 332 KB | Output is correct |
7 | Correct | 1 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 332 KB | Output is correct |
9 | Correct | 1 ms | 332 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 10 ms | 6620 KB | Output is correct |
12 | Correct | 10 ms | 6732 KB | Output is correct |
13 | Correct | 10 ms | 6732 KB | Output is correct |
14 | Correct | 9 ms | 6348 KB | Output is correct |
15 | Correct | 10 ms | 6752 KB | Output is correct |
16 | Correct | 9 ms | 6732 KB | Output is correct |
17 | Correct | 60 ms | 8008 KB | Output is correct |
18 | Correct | 56 ms | 7932 KB | Output is correct |
19 | Execution timed out | 1577 ms | 7440 KB | Time limit exceeded |
20 | Halted | 0 ms | 0 KB | - |