제출 #438122

#제출 시각아이디문제언어결과실행 시간메모리
438122josiftepeDNA 돌연변이 (IOI21_dna)C++17
0 / 100
69 ms6460 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cstring> #include "dna.h" using namespace std; const int maxn = 1e5 + 5; int a_pref_sum[maxn][4]; int b_pref_sum[maxn][4]; string a, b; vector<int> a_id[4], b_id[4]; int n; void init(string a, string b) { memset(a_pref_sum, 0, sizeof a_pref_sum); memset(b_pref_sum, 0, sizeof b_pref_sum); n = (int) a.size(); for(int i = 0; i < n; i++) { if(a[i] == 'C') a[i] = 'B'; if(b[i] == 'C') b[i] = 'B'; } for(int i = 0; i < n; i++) { if(a[i] == 'T') a[i] = 'C'; if(b[i] == 'T') b[i] = 'C'; } ::a = a; ::b = b; int cnt_a[3] = {0, 0, 0}; int cnt_b[3] = {0, 0, 0}; for(int i = 0; i < n; i++) { int id_a = (int) (a[i] - 'A'); int id_b = (int) (b[i] - 'A'); a_id[id_a].push_back(i); b_id[id_b].push_back(i); cnt_a[id_a]++; cnt_b[id_b]++; for(int j = 0; j < 3; j++) { a_pref_sum[i][j] = cnt_a[j]; b_pref_sum[i][j] = cnt_b[j]; } } } int a_query(int &x, int &y, char c) { if(x == 0) { return a_pref_sum[y][c - 'A']; } return a_pref_sum[y][c - 'A'] - a_pref_sum[x - 1][c - 'A']; } int b_query(int &x, int &y, char c) { if(x == 0) { return b_pref_sum[y][c - 'A']; } return b_pref_sum[y][c - 'A'] - b_pref_sum[x - 1][c - 'A']; } int get_distance(int x, int y) { if(a_query(x, y, 'A') == b_query(x, y, 'A') and a_query(x, y, 'B') == b_query(x, y, 'B') and a_query(x, y, 'C') == b_query(x, y, 'C')) { vector<int> v[3]; string tmp_b = b.substr(x, y - x + 1); for(int i = x, j = 0; i <= y; i++, j++) { v[b[i] - 'A'].push_back(j); } int cnt[3] = {0, 0, 0}; int ret = 0; for(int i = x, j = 0; i <= y; i++, j++) { int id_a = (a[i] - 'A'); int id_b = (tmp_b[j] - 'A'); if(id_a != id_b) { swap(tmp_b[j], tmp_b[v[id_a][cnt[id_a]]]); cnt[id_a]++; ++ret; } } return ret; } return -1; }
#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...