| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 566931 | pawned | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
int N;
int type1[100005];
int type2[100005];
int counts1[100005][3];
int counts2[100005][3];
int pfs[100005][3][3];
void init(std::string a, std::string b) {
N = a.size();
for (int i = 0; i < N; i++) {
if (a[i] == 'A')
type1[i] = 0;
else if (a[i] == 'C')
type1[i] = 1;
else
type1[i] = 2;
if (b[i] == 'A')
type2[i] = 0;
else if (b[i] == 'C')
type2[i] = 1;
else
type2[i] = 2;
}
for (int i = 0; i < 3; i++) {
counts1[0][i] = 0;
counts2[0][i] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 3; j++) {
counts1[i][j] = counts1[i - 1][j];
counts2[i][j] = counts2[i - 1][j];
}
counts1[i][type1[i - 1]]++;
counts2[i][type2[i - 1]]++;
}
/*
cout<<"counts1: "<<endl;
for (int i = 0; i < 3; i++) {
for (int j = 0; j <= N; j++) {
cout<<counts1[j][i]<<" ";
}
cout<<endl;
}
cout<<endl;
*/
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
pfs[0][i][j] = 0;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
pfs[i][j][k] = pfs[i - 1][j][k];
}
}
pfs[i][type1[i - 1]][type2[i - 1]]++;
}
}
int get_distance(int x, int y) {
int l, r;
l = x;
r = y;
bool works = true;
for (int j = 0; j < 3; j++) {
if ((counts1[r + 1][j] - counts1[l][j]) != (counts2[r + 1][j] - counts2[l][j]))
works = false;
}
if (!works)
return -1;
int vals[3][3];
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
vals[j][k] = pfs[r + 1][j][k] - pfs[l][j][k];
}
}
int total = vals[0][0] + vals[1][1] + vals[2][2];
int x1 = min(vals[0][1], vals[1][0]);
total += x1;
vals[0][1] -= x1;
vals[1][0] -= x1;
int x2 = min(vals[0][2], vals[2][0]);
total += x2;
vals[0][2] -= x2;
vals[2][0] -= x2;
int x3 = min(vals[1][2], vals[2][1]);
total += x3;
vals[1][2] -= x3;
vals[2][1] -= x3;
total += 2 * max(vals[0][1], vals[1][0], vals[0][2], vals[2][0], vals[1][2], vals[2][1]);
return total;
}