# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
591777 | triplem5ds | DNA 돌연변이 (IOI21_dna) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
///code be weshen zyk :)
#include "dna.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
#include <bits/stdc++.h>
using ll = long long;
using ii = pair<ll, ll>;
#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (ll i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (ll)(x).size()
#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define LSB(x) (__builtin_ffsll(x) - 1)
#define MSB(x) (64 - __builtin_clzll(x) - 1)
#define int ll
mt19937_64 mrand(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e5 + 5, LG = log2(N) + 1, MOD = 1e9 + 7;
int get(char c) {
if(c == 'A')
return 0;
if(c == 'C')
return 1;
return 2;
}
int cnt[N][3][3];
void init(std::string a, std::string b) {
int n= a.size();
for(int i = 0; i < n; i++) {
f(j,0,3)f(k,0,3)
cnt[i + 1][j][k] = cnt[i][j][k];
cnt[i + 1][get(a[i])][get(b[i])] += 1;
}
}
int get_distance(int x, int y) {
int l = x, r = y;
bool ok = true;
int tmp[3][3] = {};
f(j,0,3) {
int sum1 = 0, sum2 = 0;
f(k,0,3) {
sum1 += cnt[r+1][j][k] - cnt[l][j][k];
sum2 += cnt[r+1][k][j] - cnt[l][k][j];
tmp[j][k] = cnt[r+1][j][k] - cnt[l][j][k];
}
ok &= sum1 == sum2;
}
if(!ok) {
return -1;
}
int ans = 0;
int f1 = min(tmp[0][1], tmp[1][0]);
ans += f1;
tmp[0][1] -= f1; tmp[1][0] -= f1;
int f2 = min(tmp[0][2], tmp[2][0]);
ans += f2;
tmp[0][2] -= f2; tmp[2][0] -= f2;
int f3 = min(tmp[1][2], tmp[2][1]);
ans += f3;
tmp[1][2] -= f3; tmp[2][1] -= f;
int w = min({tmp[0][1],tmp[1][2],tmp[2][0]});
ans += 2 * w;
tmp[0][1] -= w;
tmp[1][2] -= w;
tmp[2][0] -= w;
int w2 = min({tmp[0][2],tmp[2][1],tmp[1][0]});
ans += 2 * w2;
tmp[0][2] -= w2;
tmp[2][1] -= w2;
tmp[1][0] -= w2;
f(i,0,3) f(j,0,3) {
if(i==j)continue;
ans += tmp[i][j];
}
return ans;
}
//void doWork() {
//
// while(q--) {
// int l, r;
// cin >> l >> r;
//
// }
//
//
//
//
//}
//int32_t main() {
//#ifdef ONLINE_JUDGE
// ios_base::sync_with_stdio(0);
// cin.tie(0);
//#endif // ONLINE_JUDGE
// int t = 1;
//// cin >> t;
// while (t--) {
// doWork();
// }
// return 0;
//}