제출 #1061394

#제출 시각아이디문제언어결과실행 시간메모리
1061394j_vdd16DNA 돌연변이 (IOI21_dna)C++17
100 / 100
35 ms8216 KiB
#include "dna.h" #include <algorithm> #include <bitset> #include <cstdint> #include <cstring> #include <iostream> #include <limits.h> #include <math.h> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <vector> //#define int long long #define loop(X, N) for(int X = 0; X < (N); X++) #define all(V) V.begin(), V.end() #define rall(V) V.rbegin(), V.rend() using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<bool> vb; typedef vector<vector<bool>> vvb; int n; vi a, b; //vi prefixA[3], prefixB[3]; vi prefix[9]; void init(string A, string B) { n = (int)A.size(); a = vi(n); b = vi(n); loop(i, n) { if (A[i] == 'A') a[i] = 0; if (A[i] == 'T') a[i] = 1; if (A[i] == 'C') a[i] = 2; if (B[i] == 'A') b[i] = 0; if (B[i] == 'T') b[i] = 1; if (B[i] == 'C') b[i] = 2; } loop(j, 9) prefix[j] = vi(n + 1); for (int i = 1; i <= n; i++) { loop(j, 9) { prefix[j][i] = prefix[j][i - 1]; } prefix[a[i - 1] * 3 + b[i - 1]][i]++; } // loop(i, 3) { // prefixA[i] = vi(n + 1); // prefixB[i] = vi(n + 1); // for (int j = 1; j <= n; j++) { // prefixA[i][j] = prefixA[i][j - 1] + (a[j - 1] == i); // prefixB[i][j] = prefixB[i][j - 1] + (b[j - 1] == i); // } // } } int get_distance(int x, int y) { // loop(i, 3) { // if (prefixA[i][y + 1] - prefixA[i][x] != prefixB[i][y + 1] - prefixB[i][x]) // return -1; // } int letterCounts[3] = { 0 }; int counts[3][3] = { 0 }; loop(j, 9) { counts[j / 3][j % 3] = prefix[j][y + 1] - prefix[j][x]; } letterCounts[0] = counts[0][1] + counts[0][2] - counts[1][0] - counts[2][0]; letterCounts[1] = counts[1][2] + counts[1][0] - counts[2][1] - counts[0][1]; letterCounts[2] = counts[2][0] + counts[2][1] - counts[0][2] - counts[1][2]; if (letterCounts[0] != 0 || letterCounts[1] != 0 || letterCounts[2] != 0) return -1; int swap1 = min(counts[1][0], counts[0][1]); counts[1][0] -= swap1; counts[0][1] -= swap1; int swap2 = min(counts[2][0], counts[0][2]); counts[2][0] -= swap2; counts[0][2] -= swap2; int swap3 = min(counts[2][1], counts[1][2]); counts[2][1] -= swap3; counts[1][2] -= swap3; int result = swap1 + swap2 + swap3; int left = (y - x + 1) - 2 * (swap1 + swap2 + swap3) - counts[0][0] - counts[1][1] - counts[2][2]; result += left / 3 * 2; return result; }
#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...