Submission #440030

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
440030	2021-07-01T13:03:50 Z	algorithm16	Mutating DNA (IOI21_dna)	C++17	100 / 100	67 ms	8752 KB

#include "dna.h"
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
string a1,b1,s="ACT";
int n,cnt[3][2][100005],p[3][3][100005];
int get_cnt(int ind1,int ind2,int l,int r) {
	if(!l) return cnt[ind1][ind2][r];
	return cnt[ind1][ind2][r]-cnt[ind1][ind2][l-1];
}
int get_p(int ind1,int ind2,int l,int r) {
	if(!l) return p[ind1][ind2][r];
	return p[ind1][ind2][r]-p[ind1][ind2][l-1];
}
void init(std::string a, std::string b) {
	n=a.size();
	for(int i=0;i<n;i++) {
		for(int j=0;j<3;j++) {
			if(a[i]==s[j]) cnt[j][0][i]=1;
			if(b[i]==s[j]) cnt[j][1][i]=1;
		}
		for(int j=0;j<3;j++) {
			for(int k=0;k<2;k++) {
				if(i) cnt[j][k][i]+=cnt[j][k][i-1];
			}
		}
		for(int j=0;j<3;j++) {
			for(int k=0;k<3;k++) {
				if(j!=k && a[i]==s[j] && b[i]==s[k]) p[j][k][i]=1;
			}
		}
		for(int j=0;j<3;j++) {
			for(int k=0;k<3;k++) {
				if(i) p[j][k][i]+=p[j][k][i-1];
			}
		}
	}
	/*for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++) {
			cout << p[i][j][n-1] << " ";
		}
	}
	cout << "\n";*/
	/*for(int i=0;i<3;i++) {
		for(int j=0;j<n;j++) {
			cout << cnt[i][0][j] << " ";
		}
		cout << "\n";
	}*/
}

int get_distance(int x, int y) {
	int diffa=get_cnt(0,0,x,y)-get_cnt(0,1,x,y);
	int diffc=get_cnt(1,0,x,y)-get_cnt(1,1,x,y);
	int difft=get_cnt(2,0,x,y)-get_cnt(2,1,x,y);
	//cout << x << " " << y << " " << diffa << " " << diffc << " " << difft << "\n";
	if(diffa!=0 || diffc!=0 || difft!=0) return -1;
	int l=0,ret=0;
	for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++) {
			l+=get_p(i,j,x,y);
		}
	}
	//cout << l << "\n";
	for(int i=0;i<3;i++) {
		for(int j=i+1;j<3;j++) {
			int sum=min(get_p(i,j,x,y),get_p(j,i,x,y));
			ret+=sum;
			l-=sum*2;
		}
	}
	return ret+(l/3)*2;
}

Subtask #1
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	7956 KB	Output is correct
2	Correct	59 ms	7992 KB	Output is correct
3	Correct	63 ms	7532 KB	Output is correct
4	Correct	55 ms	8336 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	9 ms	6732 KB	Output is correct
5	Correct	11 ms	6732 KB	Output is correct
6	Correct	9 ms	6732 KB	Output is correct
7	Correct	9 ms	6348 KB	Output is correct
8	Correct	11 ms	6696 KB	Output is correct
9	Correct	10 ms	6628 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	9 ms	6732 KB	Output is correct
5	Correct	11 ms	6732 KB	Output is correct
6	Correct	9 ms	6732 KB	Output is correct
7	Correct	9 ms	6348 KB	Output is correct
8	Correct	11 ms	6696 KB	Output is correct
9	Correct	10 ms	6628 KB	Output is correct
10	Correct	64 ms	7920 KB	Output is correct
11	Correct	56 ms	8016 KB	Output is correct
12	Correct	67 ms	7972 KB	Output is correct
13	Correct	65 ms	8076 KB	Output is correct
14	Correct	61 ms	8360 KB	Output is correct
15	Correct	61 ms	8248 KB	Output is correct
16	Correct	48 ms	8028 KB	Output is correct
17	Correct	53 ms	8068 KB	Output is correct
18	Correct	58 ms	8444 KB	Output is correct
19	Correct	43 ms	7952 KB	Output is correct
20	Correct	44 ms	8188 KB	Output is correct
21	Correct	55 ms	8448 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	2 ms	332 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	9 ms	6732 KB	Output is correct
5	Correct	11 ms	6732 KB	Output is correct
6	Correct	9 ms	6732 KB	Output is correct
7	Correct	9 ms	6348 KB	Output is correct
8	Correct	11 ms	6696 KB	Output is correct
9	Correct	10 ms	6628 KB	Output is correct
10	Correct	9 ms	6184 KB	Output is correct
11	Correct	10 ms	6860 KB	Output is correct
12	Correct	9 ms	6476 KB	Output is correct
13	Correct	10 ms	6872 KB	Output is correct
14	Correct	10 ms	6928 KB	Output is correct
15	Correct	9 ms	6988 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	7956 KB	Output is correct
2	Correct	59 ms	7992 KB	Output is correct
3	Correct	63 ms	7532 KB	Output is correct
4	Correct	55 ms	8336 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	2 ms	332 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	9 ms	6732 KB	Output is correct
12	Correct	11 ms	6732 KB	Output is correct
13	Correct	9 ms	6732 KB	Output is correct
14	Correct	9 ms	6348 KB	Output is correct
15	Correct	11 ms	6696 KB	Output is correct
16	Correct	10 ms	6628 KB	Output is correct
17	Correct	64 ms	7920 KB	Output is correct
18	Correct	56 ms	8016 KB	Output is correct
19	Correct	67 ms	7972 KB	Output is correct
20	Correct	65 ms	8076 KB	Output is correct
21	Correct	61 ms	8360 KB	Output is correct
22	Correct	61 ms	8248 KB	Output is correct
23	Correct	48 ms	8028 KB	Output is correct
24	Correct	53 ms	8068 KB	Output is correct
25	Correct	58 ms	8444 KB	Output is correct
26	Correct	43 ms	7952 KB	Output is correct
27	Correct	44 ms	8188 KB	Output is correct
28	Correct	55 ms	8448 KB	Output is correct
29	Correct	9 ms	6184 KB	Output is correct
30	Correct	10 ms	6860 KB	Output is correct
31	Correct	9 ms	6476 KB	Output is correct
32	Correct	10 ms	6872 KB	Output is correct
33	Correct	10 ms	6928 KB	Output is correct
34	Correct	9 ms	6988 KB	Output is correct
35	Correct	1 ms	480 KB	Output is correct
36	Correct	54 ms	7844 KB	Output is correct
37	Correct	61 ms	8224 KB	Output is correct
38	Correct	58 ms	8332 KB	Output is correct
39	Correct	59 ms	8584 KB	Output is correct
40	Correct	61 ms	8596 KB	Output is correct
41	Correct	8 ms	6860 KB	Output is correct
42	Correct	52 ms	8340 KB	Output is correct
43	Correct	56 ms	8608 KB	Output is correct
44	Correct	56 ms	8592 KB	Output is correct
45	Correct	48 ms	8400 KB	Output is correct
46	Correct	45 ms	8752 KB	Output is correct
47	Correct	45 ms	8704 KB	Output is correct

Submission #440030

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