# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1228320 | bornag | Mutating DNA (IOI21_dna) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef int long long;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
#define pb push_back
#define eb emplace_back
#define upb upper_bound
#define lpb lower_bound
#define ppb pop_back
#define X first
#define Y second
#define all(a) a.begin(), a.end()
#define len(a) (int) (a.size())
const ll MOD = 1e9 + 7;
const ll BASE = 32;
const int MAXN = 1e5 + 7;
int pref[MAXN][7][10];
int same[MAXN];
void init(string a, string b) {
for(int i = 0; i < len(a); i++) {
for(int j = 0; j < 2; j++)
for(int k = 0; k < 3; k++)
pref[i + 1][j][k] += pref[i][j][k];
pref[i + 1][1][(b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2))]++;
pref[i + 1][0][(a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2))]++;
same[i + 1] = same[i] + !(a[i] == b[i]);
}
}
int get_distance(int x, int y) {
x++, y++;
if(pref[y][1][0] - pref[x - 1][1][0] != pref[y][0][0] - pref[x - 1][0][0]
|| pref[y][1][1] - pref[x - 1][1][1] != pref[y][0][1] - pref[x - 1][0][1]
|| pref[y][1][2] - pref[x - 1][1][2] != pref[y][0][2] - pref[x - 1][0][2])
return -1;
return (same[y] - same[x - 1]) / 2 + ((same[y] - same[x - 1]) % 2);
}