Submission #1268323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268323		WH8	Mutating DNA (IOI21_dna)	C++20	100 / 100	21 ms	4884 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
#define iloop(x, n) for (long long i = x; i < n; ++i)
#define jloop(x, n) for (long long j = x; j < n; ++j)
#define kloop(x, n) for (long long k = x; k < n; ++k)
#define dloop(x, n) for (long long d = x; d >= n; --d)
#define ll long long
#define pll pair<long long, long long>
#define pii pair<int, int>
#define iii tuple<int, int, int>
#define vi vector<long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
#define dg(x) cout << #x << ": " << x << endl
#define all(x) x.begin(), x.end()
#define FASTIO               \
    ios::sync_with_stdio(false); \
	cin.tie(0);              \
    cout.tie(0);
#define maxn 100005

int atot[maxn], ttoc[maxn], ctoa[maxn], atoc[maxn], ctot[maxn], ttoa[maxn];
int n;


void init(std::string a, std::string b) {
	n = a.size();
	iloop(0, n){
		atot[i+1] = atot[i];
		ttoc[i+1] = ttoc[i];
		ctoa[i+1] = ctoa[i];
		atoc[i+1] = atoc[i];
		ctot[i+1] = ctot[i];
		ttoa[i+1] = ttoa[i];
		if (a[i] == b[i]);
		else {
			if (a[i] == 'A' and b[i] == 'T') atot[i+1] = atot[i] + 1;
			if (a[i] == 'T' and b[i] == 'C') ttoc[i+1] = ttoc[i] + 1;
			if (a[i] == 'C' and b[i] == 'A') ctoa[i+1] = ctoa[i] + 1;
			if (a[i] == 'A' and b[i] == 'C') atoc[i+1] = atoc[i] + 1;
			if (a[i] == 'C' and b[i] == 'T') ctot[i+1] = ctot[i] + 1;
			if (a[i] == 'T' and b[i] == 'A') ttoa[i+1] = ttoa[i] + 1;
		}
		//cout << atot[i+1] << " " <<ttoc[i+1]<<" "<<ctoa[i+1]<<" "<<atoc[i+1]<<" "<<ctot[i+1]<<" "<<ttoa[i+1]<<endl;
	}
}

int get_distance(int x, int y) {
	int ans = 0;
	int at = atot[y+1] - atot[x], tc = ttoc[y+1] - ttoc[x], ca = ctoa[y+1] - ctoa[x], ac = atoc[y+1] - atoc[x], ct = ctot[y+1] - ctot[x], ta = ttoa[y+1] - ttoa[x];
	//dg(at); dg(tc); dg(ca); dg(ac); dg(ct); dg(ta);
	//cout << endl << endl;
	
	int cur;
	cur = min(ac, ca);
	ans += cur, ac -= cur, ca -= cur;
	cur = min(at, ta);
	ans += cur, ta -= cur, at -= cur;
	cur = min(tc, ct);
	ans += cur, tc -= cur, ct -= cur;
	cur = min({at, tc, ca});
	ans += 2 * cur, at -= cur, tc -= cur, ca-=cur;
	cur = min({ac, ct, ta});
	ans += 2 * cur, ac -= cur, ct -= cur, ta-=cur;


	if (at or tc or ca or ac or ct or ta) ans = -1;
	return ans;
}

• Subtask 1: 21 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16