Submission #467486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
467486	2021-08-23T08:37:09 Z	alextodoran	Mutating DNA (IOI21_dna)	C++17	100 / 100	122 ms	23492 KB

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

typedef long long ll;

int encode (char c)
{
    if(c == 'A')
        return 0;
    if(c == 'C')
        return 1;
    if(c == 'T')
        return 2;

    assert(false);
}

vector <vector <vector <int>>> cntPref;

void init (string a, string b)
{
    int n = (int) a.size();
    cntPref = vector <vector <vector <int>>> (n, vector <vector <int>> (3, vector <int> (3)));

    for(int i = 0; i < n; i++)
    {
        if(i - 1 >= 0)
            cntPref[i] = cntPref[i - 1];
        cntPref[i][encode(a[i])][encode(b[i])]++;
    }
}

int get_distance (int x, int y)
{
    vector <vector <int>> cnt = cntPref[y];
    if(x - 1 >= 0)
    {
        for(int u = 0; u < 3; u++)
            for(int v = 0; v < 3; v++)
                cnt[u][v] -= cntPref[x - 1][u][v];
    }

    vector <int> cnta (3);
    vector <int> cntb (3);
    for(int u = 0; u < 3; u++)
        for(int v = 0; v < 3; v++)
        {
            cnta[u] += cnt[u][v];
            cntb[v] += cnt[u][v];
        }

    for(int u = 0; u < 3; u++)
        if(cnta[u] != cntb[u])
            return -1;

    int answer = 0;

    for(int u = 0; u < 3; u++)
        cnt[u][u] = 0;

    for(int u = 0; u < 3; u++)
        for(int v = u + 1; v < 3; v++)
        {
            int take = min(cnt[u][v], cnt[v][u]);
            answer += take;
            cnt[u][v] -= take;
            cnt[v][u] -= take;
        }

    int sum = 0;
    for(int u = 0; u < 3; u++)
        for(int v = 0; v < 3; v++)
            sum += cnt[u][v];
    answer += sum / 3 * 2;

    return answer;
}

Subtask #1
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	22856 KB	Output is correct
2	Correct	109 ms	23144 KB	Output is correct
3	Correct	117 ms	21280 KB	Output is correct
4	Correct	106 ms	23104 KB	Output is correct
5	Correct	0 ms	292 KB	Output is correct
6	Correct	0 ms	288 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	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	30 ms	20292 KB	Output is correct
5	Correct	33 ms	20672 KB	Output is correct
6	Correct	32 ms	20396 KB	Output is correct
7	Correct	33 ms	19184 KB	Output is correct
8	Correct	32 ms	20644 KB	Output is correct
9	Correct	31 ms	20556 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	30 ms	20292 KB	Output is correct
5	Correct	33 ms	20672 KB	Output is correct
6	Correct	32 ms	20396 KB	Output is correct
7	Correct	33 ms	19184 KB	Output is correct
8	Correct	32 ms	20644 KB	Output is correct
9	Correct	31 ms	20556 KB	Output is correct
10	Correct	105 ms	22836 KB	Output is correct
11	Correct	111 ms	23108 KB	Output is correct
12	Correct	106 ms	21956 KB	Output is correct
13	Correct	110 ms	22488 KB	Output is correct
14	Correct	122 ms	23492 KB	Output is correct
15	Correct	115 ms	23364 KB	Output is correct
16	Correct	98 ms	21960 KB	Output is correct
17	Correct	102 ms	22412 KB	Output is correct
18	Correct	101 ms	23340 KB	Output is correct
19	Correct	87 ms	22024 KB	Output is correct
20	Correct	84 ms	22520 KB	Output is correct
21	Correct	87 ms	23344 KB	Output is correct

Subtask #4
28.0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	30 ms	20292 KB	Output is correct
5	Correct	33 ms	20672 KB	Output is correct
6	Correct	32 ms	20396 KB	Output is correct
7	Correct	33 ms	19184 KB	Output is correct
8	Correct	32 ms	20644 KB	Output is correct
9	Correct	31 ms	20556 KB	Output is correct
10	Correct	28 ms	18852 KB	Output is correct
11	Correct	39 ms	20632 KB	Output is correct
12	Correct	30 ms	19320 KB	Output is correct
13	Correct	32 ms	20456 KB	Output is correct
14	Correct	39 ms	20576 KB	Output is correct
15	Correct	35 ms	20572 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	103 ms	22856 KB	Output is correct
2	Correct	109 ms	23144 KB	Output is correct
3	Correct	117 ms	21280 KB	Output is correct
4	Correct	106 ms	23104 KB	Output is correct
5	Correct	0 ms	292 KB	Output is correct
6	Correct	0 ms	288 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	30 ms	20292 KB	Output is correct
12	Correct	33 ms	20672 KB	Output is correct
13	Correct	32 ms	20396 KB	Output is correct
14	Correct	33 ms	19184 KB	Output is correct
15	Correct	32 ms	20644 KB	Output is correct
16	Correct	31 ms	20556 KB	Output is correct
17	Correct	105 ms	22836 KB	Output is correct
18	Correct	111 ms	23108 KB	Output is correct
19	Correct	106 ms	21956 KB	Output is correct
20	Correct	110 ms	22488 KB	Output is correct
21	Correct	122 ms	23492 KB	Output is correct
22	Correct	115 ms	23364 KB	Output is correct
23	Correct	98 ms	21960 KB	Output is correct
24	Correct	102 ms	22412 KB	Output is correct
25	Correct	101 ms	23340 KB	Output is correct
26	Correct	87 ms	22024 KB	Output is correct
27	Correct	84 ms	22520 KB	Output is correct
28	Correct	87 ms	23344 KB	Output is correct
29	Correct	28 ms	18852 KB	Output is correct
30	Correct	39 ms	20632 KB	Output is correct
31	Correct	30 ms	19320 KB	Output is correct
32	Correct	32 ms	20456 KB	Output is correct
33	Correct	39 ms	20576 KB	Output is correct
34	Correct	35 ms	20572 KB	Output is correct
35	Correct	1 ms	288 KB	Output is correct
36	Correct	101 ms	21252 KB	Output is correct
37	Correct	103 ms	23108 KB	Output is correct
38	Correct	110 ms	22228 KB	Output is correct
39	Correct	122 ms	23464 KB	Output is correct
40	Correct	119 ms	23476 KB	Output is correct
41	Correct	30 ms	20560 KB	Output is correct
42	Correct	104 ms	22156 KB	Output is correct
43	Correct	109 ms	23380 KB	Output is correct
44	Correct	108 ms	23380 KB	Output is correct
45	Correct	93 ms	22168 KB	Output is correct
46	Correct	84 ms	23328 KB	Output is correct
47	Correct	110 ms	23360 KB	Output is correct

Submission #467486

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