# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
437079 | 2021-06-25T18:42:18 Z | aryan12 | DNA 돌연변이 (IOI21_dna) | C++17 | 40 ms | 17292 KB |
#include "dna.h" #include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int prefA[N][3], prefB[N][3]; int pref[N][3][3]; void init(string a, string b) { int n = a.size(); int arrA[n + 1], arrB[n + 1]; for(int i = 0; i < a.size(); i++) { arrA[i + 1] = ((a[i] == 'A') ? 0 : ((a[i] == 'C') ? 1 : 2)); arrB[i + 1] = ((b[i] == 'A') ? 0 : ((b[i] == 'C') ? 1 : 2)); } for(int i = 0; i < N; i++) { for(int j = 0; j < 3; j++) { prefA[i][j] = 0; prefB[i][j] = 0; for(int k = 0; k < 3; k++) { pref[i][j][k] = 0; } } } for(int i = 1; i <= n; i++) { for(int j = 0; j < 3; j++) { prefA[i][j] = prefA[i - 1][j]; prefB[i][j] = prefB[i - 1][j]; for(int k = 0; k < 3; k++) { pref[i][j][k] = pref[i - 1][j][k]; } } prefA[i][arrA[i]]++; prefB[i][arrB[i]]++; pref[i][arrA[i]][arrB[i]]++; } } int get_distance(int x, int y) { x++, y++; if((prefA[y][0] - prefA[x - 1][0] != prefB[y][0] - prefB[x - 1][0]) || (prefA[y][1] - prefA[x - 1][1] != prefB[y][1] - prefB[x - 1][1]) || (prefA[y][2] - prefA[x - 1][2] != prefB[y][2] - prefB[x - 1][2])) { return -1; } int res = 0; int ans[3] = {0, 0, 0}; int carry[3] = {0, 0, 0}; ans[0] += min(pref[y][0][1] - pref[x - 1][0][1], pref[y][1][0] - pref[x - 1][1][0]); ans[1] += min(pref[y][0][2] - pref[x - 1][0][2], pref[y][2][0] - pref[x - 1][2][0]); ans[2] += min(pref[y][1][2] - pref[x - 1][1][2], pref[y][2][1] - pref[x - 1][2][1]); int sum = ans[0] + ans[1] + ans[2]; res = sum; int left = y - x + 1 - sum; assert(left % 3 == 0); res += (left / 3) * 2; return res; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 40 ms | 17292 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 12 ms | 12236 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 12 ms | 12236 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 12 ms | 12236 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 40 ms | 17292 KB | Execution killed with signal 6 |
2 | Halted | 0 ms | 0 KB | - |