Submission #835188

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
835188	2023-08-23T10:03:08 Z	Mohmad_Zaid	Mutating DNA (IOI21_dna)	C++17	100 / 100	31 ms	6528 KB

// #include "dna.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>one_two,two_one,two_three,three_two,one_three,three_one;
void init(string a, string b) {
    int n=a.size();
    vector<int>arr1(a.size(),0),arr2(b.size(),0);
    one_two.resize(n+1,0);
    two_one.resize(n+1,0);
    two_three.resize(n+1,0);
    three_two.resize(n+1,0);
    one_three.resize(n+1,0);
    three_one.resize(n+1,0);
    for(int i=0;i<n;i++){
        arr1[i]+=1*(a[i]=='A');
        arr1[i]+=2*(a[i]=='T');
        arr1[i]+=3*(a[i]=='C');
        arr2[i]+=1*(b[i]=='A');
        arr2[i]+=2*(b[i]=='T');
        arr2[i]+=3*(b[i]=='C');
    }
    // for(int i=0;i<n;i++)cout<<arr1[i]<<' ';cout<<endl;
    // for(int i=0;i<n;i++)cout<<arr2[i]<<' ';cout<<endl;
    for(int i=0;i<n;i++){
        int v=arr1[i]+arr2[i];
        if(a[i]!=b[i]){
            if(v==3){
                if(arr1[i]==1)one_two[i+1]=1;
                else two_one[i+1]=1;
            }else if(v==5){
                if(arr1[i]==2)two_three[i+1]=1;
                else three_two[i+1]=1;
            }else{
                if(arr1[i]==1)one_three[i+1]=1;
                else three_one[i+1]=1;
            }
        }
        one_two[i+1]+=one_two[i];
        two_one[i+1]+=two_one[i];
        two_three[i+1]+=two_three[i];
        three_two[i+1]+=three_two[i];
        one_three[i+1]+=one_three[i];
        three_one[i+1]+=three_one[i];
    }
    // for(int i=1;i<=n;i++)cout<<one_two[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<two_one[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<two_three[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<three_two[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<one_three[i]<<' ';cout<<endl;
    // for(int i=1;i<=n;i++)cout<<three_one[i]<<' ';cout<<endl;
}

int get_distance(int x, int y) {
    int sm=0;
    int o_t=one_two[y+1]-one_two[x];
    int t_o=two_one[y+1]-two_one[x];
    int t_c=two_three[y+1]-two_three[x];
    int c_t=three_two[y+1]-three_two[x];
    int o_c=one_three[y+1]-one_three[x];
    int c_o=three_one[y+1]-three_one[x];
    // cout<<o_t<<' '<<t_o<<endl;
    // cout<<t_c<<' '<<c_t<<endl;
    // cout<<o_c<<' '<<c_o<<endl;
    if((o_t+o_c)!=(c_o+t_o)){return -1;}
    if((t_o+t_c)!=(o_t+c_t)){return -1;}
    if((c_o+c_t)!=(o_c+t_c)){return -1;}
    int mn=min(o_t,t_o);
    int mn2=min(t_c,c_t);
    int mn3=min(o_c,c_o);
    // cout<<mn<<' '<<mn2<<' '<<mn3<<endl;
    o_t-=mn;t_o-=mn;
    t_c-=mn2;c_t-=mn2;
    o_c-=mn3;c_o-=mn3;
    // cout<<o_t<<' '<<t_o<<endl;
    // cout<<t_c<<' '<<c_t<<endl;
    // cout<<o_c<<' '<<c_o<<endl;
    sm+=(mn+mn2+mn3);
    sm+=(o_t+t_o+t_c+c_t+o_c+c_o)/3*2;
	return sm;
}

Subtask #1
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	6476 KB	Output is correct
2	Correct	26 ms	6452 KB	Output is correct
3	Correct	27 ms	6168 KB	Output is correct
4	Correct	28 ms	6444 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct

Subtask #2
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	300 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	5 ms	4140 KB	Output is correct
5	Correct	5 ms	4148 KB	Output is correct
6	Correct	4 ms	4180 KB	Output is correct
7	Correct	4 ms	3916 KB	Output is correct
8	Correct	4 ms	4180 KB	Output is correct
9	Correct	3 ms	4156 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	300 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	5 ms	4140 KB	Output is correct
5	Correct	5 ms	4148 KB	Output is correct
6	Correct	4 ms	4180 KB	Output is correct
7	Correct	4 ms	3916 KB	Output is correct
8	Correct	4 ms	4180 KB	Output is correct
9	Correct	3 ms	4156 KB	Output is correct
10	Correct	29 ms	6460 KB	Output is correct
11	Correct	27 ms	6456 KB	Output is correct
12	Correct	28 ms	6220 KB	Output is correct
13	Correct	29 ms	6316 KB	Output is correct
14	Correct	28 ms	6476 KB	Output is correct
15	Correct	27 ms	6452 KB	Output is correct
16	Correct	27 ms	6140 KB	Output is correct
17	Correct	27 ms	6220 KB	Output is correct
18	Correct	27 ms	6452 KB	Output is correct
19	Correct	26 ms	6100 KB	Output is correct
20	Correct	28 ms	6184 KB	Output is correct
21	Correct	28 ms	6436 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	300 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	5 ms	4140 KB	Output is correct
5	Correct	5 ms	4148 KB	Output is correct
6	Correct	4 ms	4180 KB	Output is correct
7	Correct	4 ms	3916 KB	Output is correct
8	Correct	4 ms	4180 KB	Output is correct
9	Correct	3 ms	4156 KB	Output is correct
10	Correct	4 ms	3796 KB	Output is correct
11	Correct	5 ms	4180 KB	Output is correct
12	Correct	4 ms	3996 KB	Output is correct
13	Correct	5 ms	4180 KB	Output is correct
14	Correct	5 ms	4180 KB	Output is correct
15	Correct	4 ms	4152 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	6476 KB	Output is correct
2	Correct	26 ms	6452 KB	Output is correct
3	Correct	27 ms	6168 KB	Output is correct
4	Correct	28 ms	6444 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	300 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	5 ms	4140 KB	Output is correct
12	Correct	5 ms	4148 KB	Output is correct
13	Correct	4 ms	4180 KB	Output is correct
14	Correct	4 ms	3916 KB	Output is correct
15	Correct	4 ms	4180 KB	Output is correct
16	Correct	3 ms	4156 KB	Output is correct
17	Correct	29 ms	6460 KB	Output is correct
18	Correct	27 ms	6456 KB	Output is correct
19	Correct	28 ms	6220 KB	Output is correct
20	Correct	29 ms	6316 KB	Output is correct
21	Correct	28 ms	6476 KB	Output is correct
22	Correct	27 ms	6452 KB	Output is correct
23	Correct	27 ms	6140 KB	Output is correct
24	Correct	27 ms	6220 KB	Output is correct
25	Correct	27 ms	6452 KB	Output is correct
26	Correct	26 ms	6100 KB	Output is correct
27	Correct	28 ms	6184 KB	Output is correct
28	Correct	28 ms	6436 KB	Output is correct
29	Correct	4 ms	3796 KB	Output is correct
30	Correct	5 ms	4180 KB	Output is correct
31	Correct	4 ms	3996 KB	Output is correct
32	Correct	5 ms	4180 KB	Output is correct
33	Correct	5 ms	4180 KB	Output is correct
34	Correct	4 ms	4152 KB	Output is correct
35	Correct	1 ms	300 KB	Output is correct
36	Correct	27 ms	6156 KB	Output is correct
37	Correct	28 ms	6484 KB	Output is correct
38	Correct	31 ms	6348 KB	Output is correct
39	Correct	29 ms	6460 KB	Output is correct
40	Correct	29 ms	6528 KB	Output is correct
41	Correct	3 ms	4152 KB	Output is correct
42	Correct	29 ms	6088 KB	Output is correct
43	Correct	28 ms	6448 KB	Output is correct
44	Correct	28 ms	6356 KB	Output is correct
45	Correct	27 ms	6136 KB	Output is correct
46	Correct	26 ms	6324 KB	Output is correct
47	Correct	27 ms	6328 KB	Output is correct

Submission #835188

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