Submission #739737

#	Time	Username	Problem	Language	Result	Execution time	Memory
739737		Trumling	Mutating DNA (IOI21_dna)	C++17	35 / 100	47 ms	12256 KiB

dna

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

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 999999999999
#define MOD 1000000007
#define all(x) x.begin(),x.end()

ll pre[3][100002];
vector<vector<vector<int>>>nums(2,vector<vector<int>>(3,vector<int>(100002)));
vector<vector<vector<int>>>other(3,vector<vector<int>>(3,vector<int>(100002)));

void init(string a,string b) 
{
	ll n=a.size();
	int cc[26]={ };

	cc[0]=0;
	cc['T'-'A']=1;
	cc['C'-'A']=2;

	for(int i=1;i<=n;i++)
	{
		ll aa=cc[a[i-1]-'A']; 
		ll bb=cc[b[i-1]-'A'];
		for(int j=0;j<3;j++)
			pre[j][i]=pre[j][i-1];

		for(int j=0;j<3;j++)
			for(int c=0;c<3;c++)
			{
				other[j][c][i]=other[j][c][i-1];
				if(j!=2)
				nums[j][c][i]=nums[j][c][i-1];
			}

		nums[0][aa][i]++;
		nums[1][bb][i]++;

		if(a[i-1]==b[i-1])
		continue;
		pre[aa][i]++;
		other[bb][aa][i]++;
	}

}

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

	for(int i=0;i<3;i++)
	if(nums[0][i][y]-nums[0][i][x-1]!=nums[1][i][y]-nums[1][i][x-1])
	return -1;

	ll ac=other[2][0][y]-other[2][0][x-1];
	ll ca=other[0][2][y]-other[0][2][x-1];

	ll at=other[1][0][y]-other[1][0][x-1];
	ll ta=other[0][1][y]-other[0][1][x-1];

	ll ct=other[1][2][y]-other[1][2][x-1];
	ll tc=other[2][1][y]-other[2][1][x-1];

	return max(ac,ca) + max(at,ta) + max(ct,tc);
}

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