Submission #1310650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310650		iamsazidh	Mutating DNA (IOI21_dna)	C++20	100 / 100	43 ms	22320 KiB

dna

#include "dna.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;

typedef long long              ll;
typedef double                 dl;
typedef vector<int>            vi;
typedef vector<vector<int>>    vii;
typedef vector<ll>             vl;
typedef vector<bool>           vb;
typedef pair<int,int>         pii;
typedef pair<ll, ll>          pll;

#define ff                first
#define ss                second
#define all(a)            a.begin(),a.end()
#define gcd(a,b)          __gcd(a,b)
#define lcm(a,b)          (a*(b/gcd(a,b)))
#define spc               " "

#ifdef ONLINE_JUDGE
	#define debarr(array)
	#define deb(x)
	#define del
#else
	#define debarr(array)  for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
	#define deb(x)         cerr << #x << " = " << x << endl;
	#define del cerr << '\n';
#endif


const double PI =         acos(-1);
const int MOD =           1000000007;
const int inf =           (2147483647);

vector<vii> pref;



void init(std::string a, std::string b) {
	int n = a.size();
	for(auto &x: a){
		if(x=='A') x = 0;
		if(x=='T') x = 1;
		if(x=='C') x = 2;
	}
	for(auto &x: b){
		if(x=='A') x = 0;
		if(x=='T') x = 1;
		if(x=='C') x = 2;
	}

	pref.resize(n, vii(3, vi(3, 0)));
	pref[0][a[0]][b[0]]++;
	for(int i = 1; i < n; i++){
		pref[i] = pref[i-1];
		pref[i][a[i]][b[i]]++;
	}

}

int inRange(int l, int r, int a, int b){
	return pref[r][a][b] - (l>0 ? pref[l-1][a][b] : 0);
}

bool valid(int x, int y){
	int a, b;
	a = inRange(x, y, 0, 1)+inRange(x, y, 0, 2);
	b = inRange(x, y, 2, 0)+inRange(x, y, 1, 0);
	if(a!=b) return 0;
	a = inRange(x, y, 1, 0)+inRange(x, y, 1, 2);
	b = inRange(x, y, 2, 1)+inRange(x, y, 0, 1);
	if(a!=b) return 0;
	a = inRange(x, y, 2, 1)+inRange(x, y, 2, 0);
	b = inRange(x, y, 0, 2)+inRange(x, y, 1, 2);
	if(a!=b) return 0;
	return 1;
}

int get_distance(int x, int y) {
	if(!valid(x, y)) return -1;
	int ans = inRange(x, y, 0, 1) + inRange(x, y, 0, 2);
	ans += max(inRange(x, y, 1, 2), inRange(x, y, 2, 1));
	return ans;

	return 0;
}

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