Submission #1196100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196100		dosts	Mutating DNA (IOI21_dna)	C++20	100 / 100	27 ms	12048 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
#pragma GCC target("lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define sp << " " << 
using namespace std;
const int inf = 2e18;
const int N = 2e5+1;


vi ca(N,0),ac(N,0),ct(N,0),tc(N,0),at(N,0),ta(N,0);
vi Aa(N,0),Ca(N,0),Ta(N,0),Ab(N,0),Cb(N,0),Tb(N,0);

int get(vi& v,int l,int r) {
	return v[r]-v[l-1];
}

void init(std::string a, std::string b) {
	int n = a.size();
	for (int i = 1;i<=n;i++) {
		Aa[i] = Aa[i-1]+(a[i-1] == 'A');
		Ca[i] = Ca[i-1]+(a[i-1] == 'C');
		Ta[i] = Ta[i-1]+(a[i-1] == 'T');
		Ab[i] = Ab[i-1]+(b[i-1] == 'A');
		Cb[i] = Cb[i-1]+(b[i-1] == 'C');
		Tb[i] = Tb[i-1]+(b[i-1] == 'T');
		ca[i] = ca[i-1]+(a[i-1] == 'C' && b[i-1] == 'A');
		ac[i] = ac[i-1]+(a[i-1] == 'A' && b[i-1] == 'C');
		ct[i] = ct[i-1]+(a[i-1] == 'C' && b[i-1] == 'T');
		tc[i] = tc[i-1]+(a[i-1] == 'T' && b[i-1] == 'C');
		at[i] = at[i-1]+(a[i-1] == 'A' && b[i-1] == 'T');
		ta[i] = ta[i-1]+(a[i-1] == 'T' && b[i-1] == 'A');
	}
}

int get_distance(int x, int y) {
	x++,y++;
	if (get(Aa,x,y) != get(Ab,x,y)) return -1;
	if (get(Ca,x,y) != get(Cb,x,y)) return -1;
	if (get(Ta,x,y) != get(Tb,x,y)) return -1;
	int AC = get(ac,x,y), CA = get(ca,x,y);
	int CT = get(ct,x,y), TC = get(tc,x,y);
	int AT = get(at,x,y), TA = get(ta,x,y);
	int ans = min(AC,CA)+min(CT,TC)+min(AT,TA);
	int m1 =  min(AC,CA),m2 = min(CT,TC),m3 = min(AT,TA);
	AC-=m1,CA-=m1,CT-=m2,TC-=m2,AT-=m3,TA-=m3;
	ans+=2*(AC+CA+CT+TC+AT+TA)/3;
	return ans;
}

Compilation message (stderr)

dna.cpp:13:17: warning: overflow in conversion from 'double' to 'int' changes value from '2.0e+18' to '2147483647' [-Woverflow]
   13 | const int inf = 2e18;
      |                 ^~~~

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