Submission #1215664

#TimeUsernameProblemLanguageResultExecution timeMemory
1215664vviviMutating DNA (IOI21_dna)C++20
100 / 100
24 ms9232 KiB
#include "dna.h" #include <bits/stdc++.h> using namespace std; string s, t; void myinit(string a, string b) { s = a; t = b; return; } int myget_distance(int x, int y) { string c = s.substr(x, y - x + 1); string d = t.substr(x, y - x + 1); int at = 0; int ta = 0; for (int i = 0; i < y - x + 1; i ++) { if (c[i] == 'A' && d[i] == 'T') at ++; else if (d[i] == 'A' && c[i] == 'T') ta ++; } if (at == ta) return at; else return -1; } const int maxn = 1e5 + 5; int p1[maxn][3]; int p2[maxn][3]; int p3[maxn][3][3]; int s1[maxn]; int s2[maxn]; void init(string a, string b) { memset(p1, 0, sizeof(p1)); memset(p2, 0, sizeof(p2)); memset(p3, 0, sizeof(p3)); for (int i = 0; i < a.size(); i++) { if (a[i] == 'A') s1[i] = 0; else if (a[i] == 'C') s1[i] = 1; else s1[i] = 2; if (b[i] == 'A') s2[i] = 0; else if (b[i] == 'C') s2[i] = 1; else s2[i] = 2; } p1[0][s1[0]]++; p2[0][s2[0]]++; p3[0][s1[0]][s2[0]]++; for (int i = 1; i < a.size(); i++) { for (int t1 = 0; t1 <= 2; t1++) { for (int t2 = 0; t2 <= 2; t2++) { p3[i][t1][t2] = p3[i - 1][t1][t2]; } p1[i][t1] = p1[i - 1][t1]; p2[i][t1] = p2[i - 1][t1]; } p3[i][s1[i]][s2[i]]++; p1[i][s1[i]]++; p2[i][s2[i]]++; } } int c[3][3]; int get_distance(int x, int y) { if (x == 0) { if (p1[y][0] != p2[y][0] || p1[y][1] != p2[y][1] || p1[y][2] != p2[y][2]) { return -1; } } else { if (p1[y][0] - p1[x - 1][0] != p2[y][0] - p2[x - 1][0] || p1[y][1] - p1[x - 1][1] != p2[y][1] - p2[x - 1][1] || p1[y][2] - p1[x - 1][2] != p2[y][2] - p2[x - 1][2]) { return -1; } } for (int i = 0; i <= 2; i++) { for (int j = 0; j <= 2; j++) { if (x == 0) c[i][j] = p3[y][i][j]; else c[i][j] = p3[y][i][j] - p3[x - 1][i][j]; } } int ans = 0; int all = y - x + 1; all -= c[0][0]; all -= c[1][1]; all -= c[2][2]; int h = min(c[0][1], c[1][0]); ans += h; all -= h * 2; h = min(c[0][2], c[2][0]); ans += h; all -= h * 2; h = min(c[1][2], c[2][1]); ans += h; all -= h * 2; ans += (all / 3) * 2; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...