Submission #850248

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
850248	2023-09-16T08:02:45 Z	StefanSebez	Mutating DNA (IOI21_dna)	C++17	100 / 100	119 ms	55316 KB

#include "dna.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
const int N=1e5+50;
int a[N],b[N],n,pref[N][4][3];
map<pair<int,int>,int>pmapa[N];
void init(std::string s, std::string t)
{
	n=s.size();
	for(int i=1;i<=n;i++)
	{
		if(s[i-1]==t[i-1])
		{
			a[i]=0,b[i]=0;
			continue;
		}
		if(s[i-1]=='A') a[i]=1;
		if(s[i-1]=='C') a[i]=2;
		if(s[i-1]=='T') a[i]=3;
		if(t[i-1]=='A') b[i]=1;
		if(t[i-1]=='C') b[i]=2;
		if(t[i-1]=='T') b[i]=3;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++)
		{
			for(int k=1;k<=2;k++)
			{
				pref[i][j][k]=pref[i-1][j][k];
			}
		}
		pref[i][a[i]][1]++;
		pref[i][b[i]][2]++;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=3;j++)
		{
			for(int k=1;k<=3;k++)
			{
				if(j==k)continue;
				pmapa[i][{j,k}]=pmapa[i-1][{j,k}];
			}
		}
		pmapa[i][{a[i],b[i]}]++;
		//if(a[i]==b[j] && a[j]==b[i]) par.push_back({i,j});
	}
}

int get_distance(int x, int y)
{
	x++,y++;
	int num[4][3],res=0;
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=2;j++)
		{
			num[i][j]=pref[y][i][j]-pref[x-1][i][j];
			//printf("%i %i: %i\n",i,j,num[i][j]);
		}
	}
	for(int i=1;i<=3;i++)
	{
		if(num[i][1]!=num[i][2]) return -1;
	}
	for(int i=1;i<=3;i++)
	{
		for(int j=i+1;j<=3;j++)
		{
			int a=pmapa[y][{i,j}]-pmapa[x-1][{i,j}],b=pmapa[y][{j,i}]-pmapa[x-1][{j,i}];
			//printf("%i %i %i %i: %i %i\n",x,y,i,j,a,b);
			a=min(a,b);
			num[i][1]-=a;
			num[j][1]-=a;
			res+=a;
		}
	}
	/*for(auto i:par)
	{
		if(x<=i.fi && i.se<=y)
		{
			num[a[i.fi]][1]--;
			num[a[i.se]][1]--;
			res++;
		}
	}*/
	res+=num[1][1]+num[2][1]+num[3][1]-max(num[1][1],max(num[2][1],num[3][1]));
	return res;
}

Subtask #1
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	52560 KB	Output is correct
2	Correct	113 ms	53080 KB	Output is correct
3	Correct	98 ms	48208 KB	Output is correct
4	Correct	108 ms	52120 KB	Output is correct
5	Correct	1 ms	6744 KB	Output is correct
6	Correct	1 ms	6744 KB	Output is correct
7	Correct	1 ms	6744 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6744 KB	Output is correct
2	Correct	1 ms	7000 KB	Output is correct
3	Correct	2 ms	6744 KB	Output is correct
4	Correct	57 ms	51300 KB	Output is correct
5	Correct	55 ms	51792 KB	Output is correct
6	Correct	58 ms	51284 KB	Output is correct
7	Correct	56 ms	48468 KB	Output is correct
8	Correct	62 ms	51668 KB	Output is correct
9	Correct	52 ms	53828 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6744 KB	Output is correct
2	Correct	1 ms	7000 KB	Output is correct
3	Correct	2 ms	6744 KB	Output is correct
4	Correct	57 ms	51300 KB	Output is correct
5	Correct	55 ms	51792 KB	Output is correct
6	Correct	58 ms	51284 KB	Output is correct
7	Correct	56 ms	48468 KB	Output is correct
8	Correct	62 ms	51668 KB	Output is correct
9	Correct	52 ms	53828 KB	Output is correct
10	Correct	104 ms	52560 KB	Output is correct
11	Correct	108 ms	53072 KB	Output is correct
12	Correct	105 ms	50240 KB	Output is correct
13	Correct	107 ms	51536 KB	Output is correct
14	Correct	117 ms	53628 KB	Output is correct
15	Correct	113 ms	55316 KB	Output is correct
16	Correct	103 ms	50260 KB	Output is correct
17	Correct	107 ms	51536 KB	Output is correct
18	Correct	104 ms	53584 KB	Output is correct
19	Correct	82 ms	47444 KB	Output is correct
20	Correct	78 ms	48464 KB	Output is correct
21	Correct	80 ms	50452 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	6744 KB	Output is correct
2	Correct	1 ms	7000 KB	Output is correct
3	Correct	2 ms	6744 KB	Output is correct
4	Correct	57 ms	51300 KB	Output is correct
5	Correct	55 ms	51792 KB	Output is correct
6	Correct	58 ms	51284 KB	Output is correct
7	Correct	56 ms	48468 KB	Output is correct
8	Correct	62 ms	51668 KB	Output is correct
9	Correct	52 ms	53828 KB	Output is correct
10	Correct	48 ms	47052 KB	Output is correct
11	Correct	57 ms	50768 KB	Output is correct
12	Correct	54 ms	47696 KB	Output is correct
13	Correct	59 ms	50516 KB	Output is correct
14	Correct	58 ms	50772 KB	Output is correct
15	Correct	59 ms	52048 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	108 ms	52560 KB	Output is correct
2	Correct	113 ms	53080 KB	Output is correct
3	Correct	98 ms	48208 KB	Output is correct
4	Correct	108 ms	52120 KB	Output is correct
5	Correct	1 ms	6744 KB	Output is correct
6	Correct	1 ms	6744 KB	Output is correct
7	Correct	1 ms	6744 KB	Output is correct
8	Correct	1 ms	6744 KB	Output is correct
9	Correct	1 ms	7000 KB	Output is correct
10	Correct	2 ms	6744 KB	Output is correct
11	Correct	57 ms	51300 KB	Output is correct
12	Correct	55 ms	51792 KB	Output is correct
13	Correct	58 ms	51284 KB	Output is correct
14	Correct	56 ms	48468 KB	Output is correct
15	Correct	62 ms	51668 KB	Output is correct
16	Correct	52 ms	53828 KB	Output is correct
17	Correct	104 ms	52560 KB	Output is correct
18	Correct	108 ms	53072 KB	Output is correct
19	Correct	105 ms	50240 KB	Output is correct
20	Correct	107 ms	51536 KB	Output is correct
21	Correct	117 ms	53628 KB	Output is correct
22	Correct	113 ms	55316 KB	Output is correct
23	Correct	103 ms	50260 KB	Output is correct
24	Correct	107 ms	51536 KB	Output is correct
25	Correct	104 ms	53584 KB	Output is correct
26	Correct	82 ms	47444 KB	Output is correct
27	Correct	78 ms	48464 KB	Output is correct
28	Correct	80 ms	50452 KB	Output is correct
29	Correct	48 ms	47052 KB	Output is correct
30	Correct	57 ms	50768 KB	Output is correct
31	Correct	54 ms	47696 KB	Output is correct
32	Correct	59 ms	50516 KB	Output is correct
33	Correct	58 ms	50772 KB	Output is correct
34	Correct	59 ms	52048 KB	Output is correct
35	Correct	1 ms	6744 KB	Output is correct
36	Correct	103 ms	48212 KB	Output is correct
37	Correct	117 ms	52128 KB	Output is correct
38	Correct	109 ms	49744 KB	Output is correct
39	Correct	114 ms	52544 KB	Output is correct
40	Correct	117 ms	52392 KB	Output is correct
41	Correct	62 ms	53840 KB	Output is correct
42	Correct	119 ms	49744 KB	Output is correct
43	Correct	114 ms	52584 KB	Output is correct
44	Correct	101 ms	52560 KB	Output is correct
45	Correct	75 ms	47692 KB	Output is correct
46	Correct	85 ms	50440 KB	Output is correct
47	Correct	80 ms	50308 KB	Output is correct

Submission #850248

Compilation message

Subtask #1 21.0 / 21.0

Subtask #2 22.0 / 22.0

Subtask #3 13.0 / 13.0

Subtask #4 28.0 / 28.0

Subtask #5 16.0 / 16.0

Subtask #1
21.0 / 21.0

Subtask #2
22.0 / 22.0

Subtask #3
13.0 / 13.0

Subtask #4
28.0 / 28.0

Subtask #5
16.0 / 16.0