제출 #909805

#제출 시각아이디문제언어결과실행 시간메모리
909805MarceantasyDNA 돌연변이 (IOI21_dna)C++17
0 / 100
31 ms8024 KiB
#include <bits/stdc++.h> using namespace std; int n; int pref[100000][3][3]; int pre1[100000][3], pre2[100000][3]; int matrix[3][3]; string letras = "ACT"; void init(string a, string b){ n = a.size(); memset(pref, 0, sizeof(pref)); for (int i = 0; i < n; i++){ for (int A = 0; A < 3; A++){ for (int B = 0; B < 3; B++){ if (i > 0){ pref[i][A][B] += pref[i-1][A][B]; } if (a[i] == letras[A] && b[i] == letras[B]){ pref[i][A][B]++; } } } } memset(pre1, 0, sizeof(pre1)); memset(pre2, 0, sizeof(pre2)); for (int i = 0; i < n; i++){ for (int j = 0; j < 3; j++){ if (i > 0){ pre1[i][j] = pre1[i-1][j]; pre2[i][j] = pre2[i-1][j]; } if (a[i] == letras[j]){ pre1[i][j]++; } if (b[i] == letras[j]){ pre2[i][j]++; } } } } int get_distance(int x, int y){ for(int A = 0; A < 3; A++){ if (pre1[y][A] - ( x == 0 ? 0 : pre1[x-1][A]) != pre2[y][A] - ( x == 0 ? 0 : pre2[x-1][A])){ return -1; } } for (int A = 0; A<3; ++A){ for(int B = 0; B<3; ++B){ matrix[A][B] = pref[y][A][B] - ( x == 0 ? 0 : pref[x-1][A][B]); } } int sol = 0; for (int A = 0; A<3; ++A){ for(int B = 0; B<3; ++B){ if (A == B){ continue; } int val = min(matrix[A][B], matrix[B][A]); sol += val; matrix[A][B] -= val; matrix[B][A] -= val; } } int f = 0; for (int A = 0; A<3; ++A){ for(int B = 0; B<3; ++B){ f += matrix[A][B]; } } f = f*2/3; return sol + f; }
#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...