제출 #1215649

#제출 시각아이디문제언어결과실행 시간메모리
1215649sangerafMutating DNA (IOI21_dna)C++20
100 / 100
24 ms9228 KiB
#include "dna.h" #include <bits/stdc++.h> using namespace std; string a, b; void my_init(std::string aa, std::string bb) { a = aa; b = bb; } int my_get_distance(int x, int y) { int db1=0, db2=0; for(int i=x; i<=y; i++){ if(a[i] == 'A' && b[i] == 'T') db1++; else if(a[i] == 'T' && b[i] == 'A') db2++; } if(db1 != db2) return -1; return db1; } 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 -= 2*h; h = min(c[0][2], c[2][0]); ans += h; all -= 2*h; h = min(c[1][2], c[2][1]); ans += h; all -= 2*h; ans += (all / 3) * 2; return ans; } /*void stress(){ srand(42); int n = 7; string s = "AT"; while(true){ string a, b; for(int i=0; i<n; i++){ a += s[rand() % 2]; b += s[rand() % 2]; } init(a, b); my_init(a, b); for(int i=0; i<n-1; i++){ for(int j=i; j<n-1; j++){ if(get_distance(i, j) != my_get_distance(i, j)){ cout << n << " 1\n"; cout << a << "\n" << b << "\n" << i << " " << j << endl; cout << get_distance(i, j) << endl; return; } } } } } int main(){ stress(); }*/
#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...