제출 #791473

#제출 시각아이디문제언어결과실행 시간메모리
791473acatmeowmeowDNA 돌연변이 (IOI21_dna)C++17
0 / 100
30 ms9396 KiB
#include "dna.h" #include <bits/stdc++.h> using namespace std; //#define int long long const int N = 1e5; int n, prefix1[3][N + 5], prefix2[3][N + 5], prefix[N + 5][3][3]; void init(std::string a, std::string b) { n = a.size(); a = '#' + a, b = '#' + b; for (int i= 1; i <= n; i++) { int ch = a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2); prefix1[ch][i] = 1; for (int j = 0; j < 3; j++) prefix1[j][i] += prefix1[j][i - 1]; } for (int i = 1; i <= n; i++) { int ch = b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2); prefix2[ch][i] = 1; for (int j = 0; j < 3; j++) prefix2[j][i] += prefix2[j][i - 1]; } for (int i = 1; i <= n; i++) { int ch1 = a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2); int ch2 = b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2); if (ch1 == ch2) continue; prefix[i][ch1][ch2] = 1; for (int j = 0; j < 3; j++) { for (int k = 0; k < 3; k++) { prefix[i][j][k] += prefix[i - 1][j][k]; } } } } int cnt[3][3]; int get_distance(int x, int y) { x++, y++; for (int i = 0; i < 3; i++) if(prefix1[i][y] - prefix1[i][x - 1] != prefix2[i][y] - prefix2[i][x - 1]) return -1; for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { cnt[i][j] = prefix[y][i][j] - prefix[x - 1][i][j]; } } int ans = 0; for (int i = 0; i < 3; i++) { for (int j = i + 1; j < 3; j++) { int d = min(cnt[i][j], cnt[j][i]); ans += d; cnt[i][j] -= d, cnt[j][i] -= d; } } for (int i = 0; i < 3; i++) { for (int j = 0; j < 3; j++) { if (i == j) continue; int k = 3 - i - j, d = min({cnt[i][j], cnt[j][k], cnt[k][i]}); ans += 2*d; cnt[i][j] -= d, cnt[j][k] -= d, cnt[k][i] -= d; } } return ans; } /*signed main() { int n, q; //assert(scanf("%d %d", &n, &q) == 2); cin >> n >> q; char A[n+1], B[n+1]; //assert(scanf("%s", A) == 1); //assert(scanf("%s", B) == 1); cin >> A >> B; std::string a = std::string(A); std::string b = std::string(B); std::vector<int> x(q), y(q); for (int i = 0; i < q; i++) { //assert(scanf("%d %d", &x[i], &y[i]) == 2); cin >> x[i] >> y[i]; } //fclose(stdin); std::vector<int> results(q); init(a, b); for (int i = 0; i < q; i++) { results[i] = get_distance(x[i], y[i]); } for (int i = 0; i < q; i++) { printf("%d\n", results[i]); } //fclose(stdout); return 0; }*/
#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...