Submission #437284

#	Time	Username	Problem	Language	Result	Execution time	Memory
437284		Bom164	Mutating DNA (IOI21_dna)	C++17	100 / 100	76 ms	8840 KiB

dna

#include<bits/stdc++.h>
#include<iostream>

using namespace std;

#define ll              long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define mod             1000000007
#define inf             1e18
#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define w(x)            int x; cin>>x; while(x--)

string a,b;
int n;

vector<int> cnta[3], cntb[3]; // A,T,C
vector<int> trans[6]; // AT,TA,AC,CA,TC,CT

const int A=0, T=1, C=2;
unordered_map<char,int> m = {{'A',A},{'T',T},{'C',C}};
void init(string X, string Y) {
	n=X.size();
	a=X, b=Y;
	for(int i=0;i<3;i++){ cnta[i].assign(n, 0); cntb[i].assign(n, 0); }
	for(int i=0;i<6;i++) trans[i].assign(n, 0);
	int c1,c2;
	for(int i=0;i<n;i++){
		c1 = m[X[i]]; c2 = m[Y[i]];
		cnta[c1][i] = 1;
		cntb[c2][i] = 1;
		if(c1==0 && c2==1) trans[0][i]++;
		else if(c1==1 && c2==0) trans[1][i]++;
		else if(c1==0 && c2==2) trans[2][i]++;
		else if(c1==2 && c2==0) trans[3][i]++;
		else if(c1==1 && c2==2) trans[4][i]++;
		else if(c1==2 && c2==1) trans[5][i]++;
	}
	// prefix sum
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			cnta[j][i] += cnta[j][i-1];
			cntb[j][i] += cntb[j][i-1];
		}
		for(int j=0;j<6;j++){
			trans[j][i] += trans[j][i-1];
		}
	}
}

int get_distance(int x, int y) {
	for(int i=0;i<3;i++){
		if(cnta[i][y] - (x==0?0:cnta[i][x-1]) !=  cntb[i][y] - (x==0?0:cntb[i][x-1])) return -1;
	}
	int cnt = 0;
	int q[6];
	for(int i=0;i<6;i++) q[i] = trans[i][y] - (x==0?0:trans[i][x-1]);
	cnt  = min(q[0], q[1]) + min(q[2], q[3]) + min(q[4], q[5]);
	cnt += abs(q[0] - q[1])*2;
	return cnt;
}

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