제출 #565380

#제출 시각아이디문제언어결과실행 시간메모리
565380TomkeMonkeDNA 돌연변이 (IOI21_dna)C++17
35 / 100
45 ms8180 KiB
#include <bits/stdc++.h> #include "dna.h" using namespace std; const int MAXN = 1e5 + 7; int word[MAXN]; int word2[MAXN]; int pref[MAXN][3][3]; void init(string a, string b){ int n = a.size(); for(int i = 0; i < n; i++){ if(a[i] == 'A') word[i + 1] = 0; if(a[i] == 'T') word[i + 1] = 1; if(a[i] == 'C') word[i + 1] = 2; if(b[i] == 'A') word2[i + 1] = 0; if(b[i] == 'T') word2[i + 1] = 1; if(b[i] == 'C') word2[i + 1] = 2; } for(int i = 1; i <= n; i++){ for(int c1 = 0; c1 < 3; c1++){ for(int c2 = 0; c2 < 3; c2++){ if(word[i] == c1 && word2[i] == c2) pref[i][c1][c2] = pref[i - 1][c1][c2] + 1; else pref[i][c1][c2] = pref[i - 1][c1][c2]; } } } } int get_distance(int x, int y){ x++; y++; // 0 - A, 1 - T, 2 - C // 0 -> 1 (zamiana A na T) int AT = pref[y][0][1] - pref[x - 1][0][1]; int TA = pref[y][1][0] - pref[x - 1][1][0]; int TC = pref[y][1][2] - pref[x - 1][1][2]; int CT = pref[y][2][1] - pref[x - 1][2][1]; int CA = pref[y][2][0] - pref[x - 1][2][0]; int AC = pref[y][0][2] - pref[x - 1][0][2]; if((AT + AC == TA + TC) && (TA + TC == AT + CT)){ int ans = min(AT, TA) + min(CA, AC) + min(TC, CT); ans += 2 * abs(AT - TA); return ans; } else return -1; }
#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...