Submission #580570

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580570	2022-06-21T12:41:43 Z	MODDI	Mutating DNA (IOI21_dna)	C++17	100 / 100	248 ms	13500 KB

//#include "grader.cpp"
//#include "dna.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
string str1, str2;
int n;
int tree[6][400000];
int get(char a, char b){
	if(a == 'A' && b == 'C')
		return 0;
	else if(a == 'A' && b == 'T')
		return 1;
	else if(a == 'C' && b == 'T')
		return 2;
	else if(a == 'C' && b == 'A')
		return 3;
	else if(a == 'T' && b == 'A')
		return 4;
	else 
		return 5;
}
void build(int node, int l, int r){
	if(l == r){
		if(str1[l] != str2[l])
			tree[get(str1[l], str2[l])][node] = 1;
	}
	else{
		int mid = (l + r) / 2;
		build(node * 2, l, mid);
		build(node * 2 + 1, mid + 1, r);
		tree[0][node] = tree[0][node * 2] + tree[0][node * 2 + 1];
		tree[1][node] = tree[1][node * 2] + tree[1][node * 2 + 1];
		tree[2][node] = tree[2][node * 2] + tree[2][node * 2 + 1];
		tree[3][node] = tree[3][node * 2] + tree[3][node * 2 + 1];
		tree[4][node] = tree[4][node * 2] + tree[4][node * 2 + 1];
		tree[5][node] = tree[5][node * 2] + tree[5][node * 2 + 1];
	}
}
int query(int node, int l, int r, int L, int R, int id){
	if(r < L || l > R)
		return 0;
	if(L <= l && r <= R)
		return tree[id][node];
		
	int mid = (l + r) / 2;
	int left = query(node * 2, l, mid, L, R, id);
	int right = query(node * 2 + 1, mid + 1, r, L, R, id);
	return left + right;
}
void init(string a, string b){
	n = a.size();
	str1 = a;
	str2 = b;
	memset(tree, 0, sizeof(tree));
	build(1, 0, n-1);
}
int get_distance(int x, int y) {
	int l = x, r = y;
	int calc[6];
	bool zero = true;
	for(int i = 0; i < 6; i++){
		calc[i] = query(1, 0, n-1, l, r, i);
		if(calc[i] != 0)
			zero = false;
		//cout<<calc[i]<<" ";
		//cout<<calc[i]<<endl;
	}
	//cout<<endl;
	if(zero)
		return 0;
	int ans = 0;
	int sm = min(calc[0], calc[3]);
	ans += sm;
	calc[0] -= sm;
	calc[3] -= sm;
	sm = min(calc[1], calc[4]);
	ans += sm;
	calc[1] -= sm;
	calc[4] -= sm;
	sm = min(calc[2],calc[5]);
	ans += sm;
	calc[2] -= sm;
	calc[5] -= sm;
	bool pos = true;
	if(calc[0] == 0 && calc[2] == 0 && calc[4] == 0){
		if(calc[1] == calc[3] && calc[3] == calc[5]){
			ans += calc[1] * 2;
		}
		else
			pos = false;
	} 
	else if(calc[1] == 0 && calc[3] == 0 && calc[5] == 0){
		if(calc[0] == calc[2] && calc[2] == calc[4]){
			ans += calc[0] * 2;
		}
		else
			pos = false;
	}
	else
		pos = false;
		
	if(!pos)
		return -1;
	else
		return ans;
}

Subtask #1
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	134 ms	11720 KB	Output is correct
2	Correct	129 ms	12136 KB	Output is correct
3	Correct	133 ms	12036 KB	Output is correct
4	Correct	145 ms	12132 KB	Output is correct
5	Correct	4 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	4 ms	9652 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9576 KB	Output is correct
2	Correct	4 ms	9652 KB	Output is correct
3	Correct	4 ms	9648 KB	Output is correct
4	Correct	9 ms	10664 KB	Output is correct
5	Correct	8 ms	10564 KB	Output is correct
6	Correct	8 ms	10648 KB	Output is correct
7	Correct	9 ms	10420 KB	Output is correct
8	Correct	9 ms	10440 KB	Output is correct
9	Correct	8 ms	10452 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9576 KB	Output is correct
2	Correct	4 ms	9652 KB	Output is correct
3	Correct	4 ms	9648 KB	Output is correct
4	Correct	9 ms	10664 KB	Output is correct
5	Correct	8 ms	10564 KB	Output is correct
6	Correct	8 ms	10648 KB	Output is correct
7	Correct	9 ms	10420 KB	Output is correct
8	Correct	9 ms	10440 KB	Output is correct
9	Correct	8 ms	10452 KB	Output is correct
10	Correct	139 ms	11760 KB	Output is correct
11	Correct	148 ms	11772 KB	Output is correct
12	Correct	210 ms	12084 KB	Output is correct
13	Correct	209 ms	12252 KB	Output is correct
14	Correct	248 ms	12164 KB	Output is correct
15	Correct	229 ms	12032 KB	Output is correct
16	Correct	217 ms	12108 KB	Output is correct
17	Correct	192 ms	12108 KB	Output is correct
18	Correct	207 ms	12156 KB	Output is correct
19	Correct	174 ms	12108 KB	Output is correct
20	Correct	167 ms	12136 KB	Output is correct
21	Correct	171 ms	12160 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	9576 KB	Output is correct
2	Correct	4 ms	9652 KB	Output is correct
3	Correct	4 ms	9648 KB	Output is correct
4	Correct	9 ms	10664 KB	Output is correct
5	Correct	8 ms	10564 KB	Output is correct
6	Correct	8 ms	10648 KB	Output is correct
7	Correct	9 ms	10420 KB	Output is correct
8	Correct	9 ms	10440 KB	Output is correct
9	Correct	8 ms	10452 KB	Output is correct
10	Correct	8 ms	10324 KB	Output is correct
11	Correct	9 ms	10452 KB	Output is correct
12	Correct	9 ms	10332 KB	Output is correct
13	Correct	9 ms	10580 KB	Output is correct
14	Correct	9 ms	10564 KB	Output is correct
15	Correct	8 ms	10580 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	134 ms	11720 KB	Output is correct
2	Correct	129 ms	12136 KB	Output is correct
3	Correct	133 ms	12036 KB	Output is correct
4	Correct	145 ms	12132 KB	Output is correct
5	Correct	4 ms	9684 KB	Output is correct
6	Correct	5 ms	9684 KB	Output is correct
7	Correct	4 ms	9652 KB	Output is correct
8	Correct	4 ms	9576 KB	Output is correct
9	Correct	4 ms	9652 KB	Output is correct
10	Correct	4 ms	9648 KB	Output is correct
11	Correct	9 ms	10664 KB	Output is correct
12	Correct	8 ms	10564 KB	Output is correct
13	Correct	8 ms	10648 KB	Output is correct
14	Correct	9 ms	10420 KB	Output is correct
15	Correct	9 ms	10440 KB	Output is correct
16	Correct	8 ms	10452 KB	Output is correct
17	Correct	139 ms	11760 KB	Output is correct
18	Correct	148 ms	11772 KB	Output is correct
19	Correct	210 ms	12084 KB	Output is correct
20	Correct	209 ms	12252 KB	Output is correct
21	Correct	248 ms	12164 KB	Output is correct
22	Correct	229 ms	12032 KB	Output is correct
23	Correct	217 ms	12108 KB	Output is correct
24	Correct	192 ms	12108 KB	Output is correct
25	Correct	207 ms	12156 KB	Output is correct
26	Correct	174 ms	12108 KB	Output is correct
27	Correct	167 ms	12136 KB	Output is correct
28	Correct	171 ms	12160 KB	Output is correct
29	Correct	8 ms	10324 KB	Output is correct
30	Correct	9 ms	10452 KB	Output is correct
31	Correct	9 ms	10332 KB	Output is correct
32	Correct	9 ms	10580 KB	Output is correct
33	Correct	9 ms	10564 KB	Output is correct
34	Correct	8 ms	10580 KB	Output is correct
35	Correct	4 ms	9652 KB	Output is correct
36	Correct	142 ms	13020 KB	Output is correct
37	Correct	150 ms	13148 KB	Output is correct
38	Correct	228 ms	13392 KB	Output is correct
39	Correct	233 ms	13500 KB	Output is correct
40	Correct	245 ms	13496 KB	Output is correct
41	Correct	9 ms	10580 KB	Output is correct
42	Correct	236 ms	13376 KB	Output is correct
43	Correct	200 ms	13416 KB	Output is correct
44	Correct	198 ms	13472 KB	Output is correct
45	Correct	178 ms	13384 KB	Output is correct
46	Correct	174 ms	13388 KB	Output is correct
47	Correct	189 ms	13396 KB	Output is correct

Submission #580570

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