Submission #739756

#	Time	Username	Problem	Language	Result	Execution time	Memory
739756		Trumling	Mutating DNA (IOI21_dna)	C++17	100 / 100	46 ms	12224 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=0,ca=0,at=0,ta=0,ct=0,tc=0;

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

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

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

	if(!ct && !ca || !at && !ac || !tc && !ta)
	return max(ac,ca) + max(at,ta) + max(ct,tc);

	return min(at,ta) + min(ca,ac) + min(ct,tc) + ( at + tc + ta + ct + ac + ca-2*(min(at,ta) + min(ca,ac) + min(ct,tc)))/3*2;

}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:73:9: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |  if(!ct && !ca || !at && !ac || !tc && !ta)
      |     ~~~~^~~~~~
dna.cpp:73:37: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   73 |  if(!ct && !ca || !at && !ac || !tc && !ta)
      |                                 ~~~~^~~~~~

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