제출 #444336

#제출 시각아이디문제언어결과실행 시간메모리
444336computerboxDNA 돌연변이 (IOI21_dna)C++17
0 / 100
57 ms6936 KiB
#include "dna.h" #include <bits/stdc++.h> using namespace std; int preff[100010][3][3]; int num[27]; void init(string a, string b) { num['A'-'A']=0; num['T'-'A']=1; num['C'-'A']=2; for(int i = 0; i < (int)a.size(); i++) { int x = num[a[i] - 'A']; int y = num[b[i] - 'A']; preff[i][x][y]++; if(i != 0) { for(int x = 0; x < 3; x++) { for(int y = 0; y < 3; y++) { preff[i][x][y] += preff[i - 1][x][y]; } } } } } int get_distance(int x, int y) { int cnt[3][3]; memset(cnt,0,sizeof(cnt)); if(x == 0) { for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { cnt[i][j]+=preff[y][i][j]; } } } else { for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { cnt[i][j]+=(preff[y][i][j]-preff[x-1][i][j]); } } } int ans=0; for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { int cycle_2 = min(cnt[i][j],cnt[j][i]); ans += cycle_2; cnt[i][j] -= cycle_2; cnt[j][i] -= cycle_2; } } for(int i = 0; i < 3; i++) { for(int j = 0; j < 3; j++) { for(int k = 0; k < 3; k++) { int cycle_3 = min(cnt[i][j],min(cnt[j][k],cnt[k][i])); ans += cycle_3 * 2; cnt[i][j] -= cycle_3; cnt[j][k] -= cycle_3; cnt[k][i] -= cycle_3; } } } 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...