제출 #493599

#제출 시각아이디문제언어결과실행 시간메모리
493599TranGiaHuy1508DNA 돌연변이 (IOI21_dna)C++17
100 / 100
47 ms8880 KiB
#include "bits/stdc++.h" using namespace std; typedef vector<int> vi; int cv(char c){ if (c == 'A') return 0; if (c == 'T') return 1; return 2; } vi pfxa[3], pfxb[3]; vi pfx[6]; int n; string a, b; void init(string A, string B){ a = A; b = B; n = a.length(); for (int i=0; i<3; i++) pfxa[i].assign(n, 0); for (int i=0; i<3; i++) pfxb[i].assign(n, 0); for (int i=0; i<6; i++) pfx[i].assign(n, 0); for (int i=0; i<n; i++){ for (int j=0; j<3; j++){ pfxa[j][i] = (i == 0 ? 0 : pfxa[j][i-1]) + (j == cv(a[i])); } } for (int i=0; i<n; i++){ for (int j=0; j<3; j++){ pfxb[j][i] = (i == 0 ? 0 : pfxb[j][i-1]) + (j == cv(b[i])); } } for (int i=0; i<n; i++){ for (int j=0; j<6; j++){ pfx[j][i] = (i == 0 ? 0 : pfx[j][i-1]); } if (a[i] == 'A' && b[i] == 'T') pfx[0][i]++; if (a[i] == 'T' && b[i] == 'A') pfx[1][i]++; if (a[i] == 'A' && b[i] == 'C') pfx[2][i]++; if (a[i] == 'C' && b[i] == 'A') pfx[3][i]++; if (a[i] == 'T' && b[i] == 'C') pfx[4][i]++; if (a[i] == 'C' && b[i] == 'T') pfx[5][i]++; } } int get_distance(int x, int y){ if (x == 0){ if (pfxa[0][y] != pfxb[0][y]){ return -1; } if (pfxa[1][y] != pfxb[1][y]){ return -1; } if (pfxa[2][y] != pfxb[2][y]){ return -1; } } else{ if ((pfxa[0][y] - pfxa[0][x-1]) != (pfxb[0][y] - pfxb[0][x-1])){ return -1; } if ((pfxa[1][y] - pfxa[1][x-1]) != (pfxb[1][y] - pfxb[1][x-1])){ return -1; } if ((pfxa[2][y] - pfxa[2][x-1]) != (pfxb[2][y] - pfxb[2][x-1])){ return -1; } } int ca = pfx[0][y] - (x == 0 ? 0 : pfx[0][x-1]); int cb = pfx[1][y] - (x == 0 ? 0 : pfx[1][x-1]); int cc = pfx[2][y] - (x == 0 ? 0 : pfx[2][x-1]); int cd = pfx[3][y] - (x == 0 ? 0 : pfx[3][x-1]); int ce = pfx[4][y] - (x == 0 ? 0 : pfx[4][x-1]); int cf = pfx[5][y] - (x == 0 ? 0 : pfx[5][x-1]); int res = 0; int m1 = min(ca, cb), m2 = min(cc, cd), m3 = min(ce, cf); res += m1 + m2 + m3; ca -= m1; cb -= m1; cc -= m2; cd -= m2; ce -= m3; cf -= m3; res += 2 * (ca + cb); return res; } #ifdef LOCAL int main(){ string A, B; cin >> A >> B; init(A, B); int q; cin >> q; for (int i=0; i<q; i++){ int x, y; cin >> x >> y; cout << get_distance(x, y) << "\n"; } } #endif
#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...