제출 #576712

#제출 시각아이디문제언어결과실행 시간메모리
576712MohamedFaresNebiliDNA 돌연변이 (IOI21_dna)C++17
100 / 100
56 ms11504 KiB
#include <bits/stdc++.h> #include "dna.h" #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; using ll = long long; using ii = pair<int, int>; using vi = vector<int>; #define pb push_back #define pp pop_back #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define lb lower_bound #define ub upper_bound typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; int P[100001][3], Pr[100001][3]; int M[100001][3], A[100001][3][3]; string S, T; int N; void init(string a, string b) { S = a, T = b; N = S.length(); vector<int> U, V; for(int l = 0; l < N; l++) { if(S[l] == 'A') U.pb(0); if(S[l] == 'C') U.pb(1); if(S[l] == 'T') U.pb(2); if(T[l] == 'A') V.pb(0); if(T[l] == 'C') V.pb(1); if(T[l] == 'T') V.pb(2); } for(int l = 0; l < N; l++) { P[l][U[l]]++; Pr[l][V[l]]++; M[l][U[l]] += (S[l] != T[l]); A[l][U[l]][V[l]]++; for(int i = 0; i < 3 && l > 0; i++) { P[l][i] += P[l - 1][i]; Pr[l][i] += Pr[l - 1][i]; M[l][i] += M[l - 1][i]; for(int j = 0; j < 3; j++) A[l][i][j] += A[l - 1][i][j]; } } } int get_distance(int x, int y) { for(int l = 0; l < 3; l++) { int X = P[y][l], Y = Pr[y][l]; if(x) X -= P[x - 1][l], Y -= Pr[x - 1][l]; if(X != Y) return -1; } int best = 1e9 + 7; for(int l = 0; l < 3; l++) { int res = M[y][l]; if(x) res -= M[x - 1][l]; int X = (l + 1) % 3, Y = (l + 2) % 3; int U = M[y][X], V = M[y][Y]; if(x) U -= M[x - 1][X], V -= M[x - 1][Y]; int u = A[y][l][X], uu = A[y][X][l]; if(x) u -= A[x - 1][l][X], uu -= A[x - 1][X][l]; int v = A[y][l][Y], vv = A[y][Y][l]; if(x) v -= A[x - 1][l][Y], vv -= A[x - 1][Y][l]; U -= min(u, uu), V -= min(v, vv); res += min(U, V); best = min(best, res); } return best; }
#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...