Submission #861259

#	Time	Username	Problem	Language	Result	Execution time	Memory
861259		midi	Mutating DNA (IOI21_dna)	C++17	100 / 100	40 ms	13592 KiB

dna

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define float long double
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef unordered_map<ll,ll> umapll;

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend()
#define in(s,x) ((s).find((x)) != (s).end())

#define mxN 100'010ll
#define INF (LLONG_MAX>>2ll)
#define MOD 1'000'000'007ll

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

ll n;
vc<char> a(mxN), b(mxN);

vcll aca(mxN, 0), caa(mxN, 0), ata(mxN, 0), taa(mxN, 0), cta(mxN, 0), tca(mxN, 0);

vcll cntaa(mxN, 0), cntca(mxN, 0), cntta(mxN, 0);
vcll cntab(mxN, 0), cntcb(mxN, 0), cnttb(mxN, 0);

inline void build_pcas ()
{
	ll i;

	f0r(i,1,n)
	{
		a[i]+=32;
		b[i]+=32;
	}

	f0r(i,1,n)
	{
		char c1=a[i], c2=b[i];

		cntaa[i] = cntaa[i-1] + (c1=='a');
		cntab[i] = cntab[i-1] + (c2=='a');

		cntca[i] = cntca[i-1] + (c1=='c');
		cntcb[i] = cntcb[i-1] + (c2=='c');

		cntta[i] = cntta[i-1] + (c1=='t');
		cnttb[i] = cnttb[i-1] + (c2=='t');

		aca[i] = aca[i-1] + (c1=='a' && c2=='c');
		caa[i] = caa[i-1] + (c1=='c' && c2=='a');
		ata[i] = ata[i-1] + (c1=='a' && c2=='t');
		taa[i] = taa[i-1] + (c1=='t' && c2=='a');
		cta[i] = cta[i-1] + (c1=='c' && c2=='t');
		tca[i] = tca[i-1] + (c1=='t' && c2=='c');
	}
}

void init (string s1, string s2)
{
	ll i;
	n=s1.sz();
	f0r(i,0,n-1)
	{
		a[i+1]=s1[i];
		b[i+1]=s2[i];
	}

	build_pcas();
}

int get_distance (int x, int y)
{
	y++;

	if ((cntaa[y]-cntaa[x] != cntab[y]-cntab[x]) || (cntca[y]-cntca[x] != cntcb[y]-cntcb[x])) return -1;

	ll ac=aca[y]-aca[x];
	ll at=ata[y]-ata[x];
	ll ca=caa[y]-caa[x];
	ll ta=taa[y]-taa[x];
	ll ct=cta[y]-cta[x];
	ll tc=tca[y]-tca[x];

	/*
	printf("ac: %lli\n", ac);
	printf("ca: %lli\n", ca);
	printf("at: %lli\n", at);
	printf("ta: %lli\n", ta);
	printf("ct: %lli\n", ct);
	printf("tc: %lli\n", tc);
	*/

	ll s = min(ac, ca) + min(at, ta) + min(ct, tc);

	ac = abs(ac-ca);
	ct = abs(ct-tc);
	ta = abs(ta-at);

	/*
	printf("ac: %lli\n", ac);
	printf("ct: %lli\n", ct);
	printf("ta: %lli\n", ta);
	*/

	s+=2*ac;

	return s;
}

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