제출 #977386

#제출 시각아이디문제언어결과실행 시간메모리
977386sstojilkovic19DNA 돌연변이 (IOI21_dna)C++17
100 / 100
46 ms9172 KiB
#include "dna.h" #include <bits/stdc++.h> using namespace std; string aa, bb; int n = 100010; vector<vector<int>> pref(7, vector<int>(n, 0)), cnt1(3, vector<int>(n, 0)), cnt2(3, vector<int>(n, 0)); void init(std::string a, std::string b) { aa = " " + a; bb = " " + b; n = a.length(); /* 0 uk 1 AT 2 TA 3 AC 4 CA 5 TC 6 CT */ a = " " + a; b = " " + b; for (int i = 0; i <= 6; i++) { for (int j = 1; j <= n; j++) { cnt1[0][j] = cnt1[0][j - 1]; cnt1[1][j] = cnt1[1][j - 1]; cnt1[2][j] = cnt1[2][j - 1]; cnt2[0][j] = cnt2[0][j - 1]; cnt2[1][j] = cnt2[1][j - 1]; cnt2[2][j] = cnt2[2][j - 1]; if (a[j] == 'A') cnt1[0][j]++; else if (a[j] == 'T') cnt1[1][j]++; else cnt1[2][j]++; if (b[j] == 'A') cnt2[0][j]++; else if (b[j] == 'T') cnt2[1][j]++; else cnt2[2][j]++; pref[i][j] = pref[i][j - 1]; if (i == 0 && a[j] != b[j]) pref[i][j]++; else if (i == 1 && a[j] == 'A' && b[j] == 'T') pref[i][j]++; else if (i == 2 && a[j] == 'T' && b[j] == 'A') pref[i][j]++; else if (i == 3 && a[j] == 'A' && b[j] == 'C') pref[i][j]++; else if (i == 4 && a[j] == 'C' && b[j] == 'A') pref[i][j]++; else if (i == 5 && a[j] == 'T' && b[j] == 'C') pref[i][j]++; else if (i == 6 && a[j] == 'C' && b[j] == 'T') pref[i][j]++; } } } int get_distance(int x, int y) { x++; y++; if (cnt1[0][y] - cnt1[0][x - 1] != cnt2[0][y] - cnt2[0][x - 1] || cnt1[1][y] - cnt1[1][x - 1] != cnt2[1][y] - cnt2[1][x - 1] || cnt1[2][y] - cnt1[2][x - 1] != cnt2[2][y] - cnt2[2][x - 1]) { return -1; } int cnt = 0; cnt += min(pref[1][y] - pref[1][x - 1], pref[2][y] - pref[2][x - 1]); cnt += min(pref[3][y] - pref[3][x - 1], pref[4][y] - pref[4][x - 1]); cnt += min(pref[5][y] - pref[5][x - 1], pref[6][y] - pref[6][x - 1]); int uk = pref[0][y] - pref[0][x - 1]; int ans = cnt + 2 * (uk - 2 * cnt) / 3; //cout<<cnt<<" "<<uk<<"\n"; //cout<<pref[0][y]<<" "<<pref[0][x-1]<<"\n"; 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...