oj.uz

Submission #607648

# Submission time Handle Problem Language Result Execution time Memory
607648 2022-07-26T22:55:41 Z jairRS Mutating DNA (IOI21_dna) C++17
100 / 100
 272 ms 66812 KB 
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

string ga, gb;
map<char, vi> prefixCharA, prefixCharB;
// prefix array of the positions where [c1][c2] c2 is in b instead of c1
map<char, map<char, int>> inPlaceOf[(int)1e5 + 1];

char characters[3] = {'A', 'T', 'C'};

void init(string a, string b)
{
    int n = a.size();
    ga = ' ' + a;
    gb = ' ' + b;

    for (char c : characters)
    {
        prefixCharA[c] = prefixCharB[c] = vi(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            prefixCharA[c][i] = (ga[i] == c) + prefixCharA[c][i - 1];
            prefixCharB[c][i] = (gb[i] == c) + prefixCharB[c][i - 1];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
            {
                if (k == j)
                    continue;
                inPlaceOf[i][characters[j]][characters[k]] =
                    inPlaceOf[i - 1][characters[j]][characters[k]];
            }

        if (ga[i] != gb[i])
            inPlaceOf[i][ga[i]][gb[i]]++;
    }
}

int get_distance(int x, int y)
{
    x++, y++;

    bool pos = true;
    for (char c : characters)
    {
        int countInA = prefixCharA[c][y] - prefixCharA[c][x - 1];
        int countInB = prefixCharB[c][y] - prefixCharB[c][x - 1];
        pos &= (countInA == countInB);
    }

    if (!pos)
        return -1;

    map<char, map<char, int>> countIPO;
    for (int j = 0; j < 3; j++)
        for (int k = j + 1; k < 3; k++)
        {
            char c1 = characters[j], c2 = characters[k];
            countIPO[c1][c2] = inPlaceOf[y][c1][c2] - inPlaceOf[x - 1][c1][c2];
            countIPO[c2][c1] = inPlaceOf[y][c2][c1] - inPlaceOf[x - 1][c2][c1];
        }

    int moves = 0, leftover = 0;

    for (int j = 0; j < 3; j++)
        for (int k = j + 1; k < 3; k++)
        {
            char c1 = characters[j], c2 = characters[k];
            int dif = min(countIPO[c1][c2], countIPO[c2][c1]);
            countIPO[c1][c2] -= dif;
            countIPO[c2][c1] -= dif;
            moves += dif;

            leftover += countIPO[c1][c2];
            leftover += countIPO[c2][c1];
        }

    moves += 2 * leftover / 3;

    return moves;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 65124 KB Output is correct
2 Correct 221 ms 65832 KB Output is correct
3 Correct 246 ms 60620 KB Output is correct
4 Correct 223 ms 66040 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5000 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 111 ms 63648 KB Output is correct
5 Correct 121 ms 64468 KB Output is correct
6 Correct 103 ms 63968 KB Output is correct
7 Correct 93 ms 60316 KB Output is correct
8 Correct 98 ms 64388 KB Output is correct
9 Correct 101 ms 64436 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 111 ms 63648 KB Output is correct
5 Correct 121 ms 64468 KB Output is correct
6 Correct 103 ms 63968 KB Output is correct
7 Correct 93 ms 60316 KB Output is correct
8 Correct 98 ms 64388 KB Output is correct
9 Correct 101 ms 64436 KB Output is correct
10 Correct 236 ms 65052 KB Output is correct
11 Correct 228 ms 65764 KB Output is correct
12 Correct 256 ms 62072 KB Output is correct
13 Correct 264 ms 63568 KB Output is correct
14 Correct 219 ms 66176 KB Output is correct
15 Correct 238 ms 66108 KB Output is correct
16 Correct 214 ms 62084 KB Output is correct
17 Correct 210 ms 63500 KB Output is correct
18 Correct 272 ms 66132 KB Output is correct
19 Correct 219 ms 62156 KB Output is correct
20 Correct 174 ms 63544 KB Output is correct
21 Correct 194 ms 66204 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 111 ms 63648 KB Output is correct
5 Correct 121 ms 64468 KB Output is correct
6 Correct 103 ms 63968 KB Output is correct
7 Correct 93 ms 60316 KB Output is correct
8 Correct 98 ms 64388 KB Output is correct
9 Correct 101 ms 64436 KB Output is correct
10 Correct 106 ms 59276 KB Output is correct
11 Correct 103 ms 64640 KB Output is correct
12 Correct 94 ms 60680 KB Output is correct
13 Correct 105 ms 64400 KB Output is correct
14 Correct 106 ms 64652 KB Output is correct
15 Correct 112 ms 64604 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 65124 KB Output is correct
2 Correct 221 ms 65832 KB Output is correct
3 Correct 246 ms 60620 KB Output is correct
4 Correct 223 ms 66040 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Correct 2 ms 5000 KB Output is correct
8 Correct 2 ms 4948 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct
11 Correct 111 ms 63648 KB Output is correct
12 Correct 121 ms 64468 KB Output is correct
13 Correct 103 ms 63968 KB Output is correct
14 Correct 93 ms 60316 KB Output is correct
15 Correct 98 ms 64388 KB Output is correct
16 Correct 101 ms 64436 KB Output is correct
17 Correct 236 ms 65052 KB Output is correct
18 Correct 228 ms 65764 KB Output is correct
19 Correct 256 ms 62072 KB Output is correct
20 Correct 264 ms 63568 KB Output is correct
21 Correct 219 ms 66176 KB Output is correct
22 Correct 238 ms 66108 KB Output is correct
23 Correct 214 ms 62084 KB Output is correct
24 Correct 210 ms 63500 KB Output is correct
25 Correct 272 ms 66132 KB Output is correct
26 Correct 219 ms 62156 KB Output is correct
27 Correct 174 ms 63544 KB Output is correct
28 Correct 194 ms 66204 KB Output is correct
29 Correct 106 ms 59276 KB Output is correct
30 Correct 103 ms 64640 KB Output is correct
31 Correct 94 ms 60680 KB Output is correct
32 Correct 105 ms 64400 KB Output is correct
33 Correct 106 ms 64652 KB Output is correct
34 Correct 112 ms 64604 KB Output is correct
35 Correct 3 ms 5000 KB Output is correct
36 Correct 223 ms 61116 KB Output is correct
37 Correct 242 ms 66328 KB Output is correct
38 Correct 214 ms 63064 KB Output is correct
39 Correct 250 ms 66812 KB Output is correct
40 Correct 224 ms 66620 KB Output is correct
41 Correct 113 ms 64596 KB Output is correct
42 Correct 251 ms 63072 KB Output is correct
43 Correct 227 ms 66716 KB Output is correct
44 Correct 249 ms 66708 KB Output is correct
45 Correct 179 ms 63032 KB Output is correct
46 Correct 183 ms 66684 KB Output is correct
47 Correct 209 ms 66684 KB Output is correct