| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 791472 | acatmeowmeow | Mutating DNA (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}*/