제출 #1190138

#제출 시각아이디문제언어결과실행 시간메모리
1190138MrDogMeatMutating DNA (IOI21_dna)C++20
100 / 100
24 ms5644 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; int enc[256]; int N, A[MAXN], B[MAXN]; int cnt[MAXN], cc[3][MAXN], pref[2][MAXN]; void init(std::string a, std::string b) { enc['A'] = 0; enc['C'] = 1; enc['T'] = 2; int N = a.size(); for(int i = 0; i < N; i++) { A[i + 1] = enc[a[i]]; B[i + 1] = enc[b[i]]; } for(int i = 1; i <= N; i++) { for(int j = 0; j < 3; j++) { cc[j][i] = cc[j][i - 1]; } cnt[i] = cnt[i - 1]; pref[0][i] = pref[0][i - 1]; pref[1][i] = pref[1][i - 1]; cc[A[i]][i]++; cc[B[i]][i]--; if(A[i] != B[i]) { cnt[i]++; if(A[i] == 0 && B[i] == 1) { pref[0][i]++; } if(A[i] == 1 && B[i] == 0) { pref[1][i]++; } } } } int get_distance(int x, int y) { x++, y++; for(int j = 0; j < 3; j++) { if(cc[j][y] - cc[j][x - 1] != 0) { return -1; } } int D = (pref[0][y] - pref[0][x - 1]) - (pref[1][y] - pref[1][x - 1]); if(D < 0) D = -D; int Ans = (cnt[y] - cnt[x - 1] - 3*D) / 2 + 2*D; 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...