| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1290177 | blackscreen1 | DNA 돌연변이 (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include "dna_ioi.h"
#include <bits//stdc++.h>
using namespace std;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll pfa[3][1000005], pfb[3][1000005], pfc[6][100005], n;
ll ar[6], ans, k, s;
void init(string a, string b) {
n = a.length();
iloop(0, n) {
jloop(0, 3) pfa[j][i+1] = pfa[j][i];
jloop(0, 3) pfb[j][i+1] = pfb[j][i];
jloop(0, 6) pfc[j][i+1] = pfc[j][i];
if (a[i] == 'A') pfa[0][i+1]++;
if (a[i] == 'C') pfa[1][i+1]++;
if (a[i] == 'T') pfa[2][i+1]++;
if (b[i] == 'A') pfb[0][i+1]++;
if (b[i] == 'C') pfb[1][i+1]++;
if (b[i] == 'T') pfb[2][i+1]++;
if (a[i] == 'A' && b[i] == 'C') pfc[0][i+1]++;
if (a[i] == 'A' && b[i] == 'T') pfc[1][i+1]++;
if (a[i] == 'C' && b[i] == 'A') pfc[2][i+1]++;
if (a[i] == 'C' && b[i] == 'T') pfc[3][i+1]++;
if (a[i] == 'T' && b[i] == 'A') pfc[4][i+1]++;
if (a[i] == 'T' && b[i] == 'C') pfc[5][i+1]++;
}
}
int get_distance(int x, int y) {
s = 0;
iloop(0, 3) if (pfa[i][y+1] - pfa[i][x] != pfb[i][y+1] - pfb[i][x]) return -1;
ans = 0;
iloop(0, 6) {ar[i] = pfc[i][y+1] - pfc[i][x]; s += ar[i];}
k = min(ar[0], ar[2]);
ans += k;
s -= 2*k;
k = min(ar[1], ar[4]);
ans += k;
s -= 2*k;
k = min(ar[3], ar[5]);
ans += k;
s -= 2*k;
return ans + s/3*2;
}