oj.uz

Submission #600886

# Submission time Handle Problem Language Result Execution time Memory
600886 2022-07-21T08:47:39 Z Valaki2 Mutating DNA (IOI21_dna) C++17
100 / 100
 145 ms 35272 KB 
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

#define a A
#define b B
#define x X
#define y Y

#define pb push_back

int n;
vector<int> a;
vector<int> b;
vector<vector<int> > pref_cnt_a;
vector<vector<int> > pref_cnt_b;
vector<vector<vector<int> > > pref;

void solve() {
    pref_cnt_a.assign(1 + n, vector<int> (3, 0));
    pref_cnt_b.assign(1 + n, vector<int> (3, 0));
    for(int i = 1; i <= n; i++) {
        pref_cnt_a[i] = pref_cnt_a[i - 1];
        pref_cnt_a[i][a[i]]++;
        pref_cnt_b[i] = pref_cnt_b[i - 1];
        pref_cnt_b[i][b[i]]++;
    }
    pref.assign(1 + n, vector<vector<int> > (3, vector<int> (3, 0)));
    for(int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1];
        pref[i][a[i]][b[i]]++;
    }
}

int query(int l, int r) {
    int res = 0;
    vector<int> cnt_a(3, 0);
    vector<int> cnt_b(3, 0);
    for(int i = 0; i < 3; i++) {
        cnt_a[i] = pref_cnt_a[r][i] - pref_cnt_a[l - 1][i];
        cnt_b[i] = pref_cnt_b[r][i] - pref_cnt_b[l - 1][i];
        if(cnt_a[i] != cnt_b[i]) {
            return -1;
        }
    }
    vector<vector<int> > v(3, vector<int> (3, 0));
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            v[i][j] = pref[r][i][j] - pref[l - 1][i][j];
        }
        v[i][i] = 0;
    }
    int mini = -1;
    mini = min(v[0][1], v[1][0]);
    res += mini;
    v[0][1] -= mini;
    v[1][0] -= mini;
    mini = min(v[2][1], v[1][2]);
    res += mini;
    v[2][1] -= mini;
    v[1][2] -= mini;
    mini = min(v[0][2], v[2][0]);
    res += mini;
    v[0][2] -= mini;
    v[2][0] -= mini;
    mini = -1;
    int maxi = 0;
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            maxi = max(maxi, v[i][j]);
        }
    }
    res += 2 * maxi;
    return res;
}

#undef a
#undef b
#undef x
#undef y
void init(string a, string b) {
    n = a.size();
    A.assign(n + 1, 0);
    B.assign(n + 1, 0);
    for(int i = 1; i <= n; i++) {
        if(a[i - 1] == 'A') {
            A[i] = 0;
        }
        if(a[i - 1] == 'T') {
            A[i] = 1;
        }
        if(a[i - 1] == 'C') {
            A[i] = 2;
        }
        if(b[i - 1] == 'A') {
            B[i] = 0;
        }
        if(b[i - 1] == 'T') {
            B[i] = 1;
        }
        if(b[i - 1] == 'C') {
            B[i] = 2;
        }
    }
    solve();
}

int get_distance(int x, int y) {
	return query(x + 1, y + 1);
}

/*
23 1
AAAAAAAAAACCCCCCCCCCCCTTTTTTTTTTT
CCCCTTTTTTAAAAAAATTTTTAAACCCCCCCC
0 22
*/

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 34596 KB Output is correct
2 Correct 120 ms 34844 KB Output is correct
3 Correct 129 ms 32008 KB Output is correct
4 Correct 121 ms 34856 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 45 ms 32008 KB Output is correct
5 Correct 43 ms 32332 KB Output is correct
6 Correct 53 ms 32048 KB Output is correct
7 Correct 39 ms 30188 KB Output is correct
8 Correct 40 ms 32384 KB Output is correct
9 Correct 40 ms 32288 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 45 ms 32008 KB Output is correct
5 Correct 43 ms 32332 KB Output is correct
6 Correct 53 ms 32048 KB Output is correct
7 Correct 39 ms 30188 KB Output is correct
8 Correct 40 ms 32384 KB Output is correct
9 Correct 40 ms 32288 KB Output is correct
10 Correct 133 ms 34500 KB Output is correct
11 Correct 122 ms 34884 KB Output is correct
12 Correct 126 ms 32992 KB Output is correct
13 Correct 127 ms 33712 KB Output is correct
14 Correct 126 ms 35220 KB Output is correct
15 Correct 134 ms 35092 KB Output is correct
16 Correct 136 ms 32832 KB Output is correct
17 Correct 142 ms 33708 KB Output is correct
18 Correct 119 ms 35108 KB Output is correct
19 Correct 108 ms 32912 KB Output is correct
20 Correct 109 ms 33768 KB Output is correct
21 Correct 88 ms 35116 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 45 ms 32008 KB Output is correct
5 Correct 43 ms 32332 KB Output is correct
6 Correct 53 ms 32048 KB Output is correct
7 Correct 39 ms 30188 KB Output is correct
8 Correct 40 ms 32384 KB Output is correct
9 Correct 40 ms 32288 KB Output is correct
10 Correct 38 ms 29664 KB Output is correct
11 Correct 44 ms 32320 KB Output is correct
12 Correct 42 ms 30228 KB Output is correct
13 Correct 42 ms 32096 KB Output is correct
14 Correct 42 ms 32288 KB Output is correct
15 Correct 43 ms 32372 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 34596 KB Output is correct
2 Correct 120 ms 34844 KB Output is correct
3 Correct 129 ms 32008 KB Output is correct
4 Correct 121 ms 34856 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 45 ms 32008 KB Output is correct
12 Correct 43 ms 32332 KB Output is correct
13 Correct 53 ms 32048 KB Output is correct
14 Correct 39 ms 30188 KB Output is correct
15 Correct 40 ms 32384 KB Output is correct
16 Correct 40 ms 32288 KB Output is correct
17 Correct 133 ms 34500 KB Output is correct
18 Correct 122 ms 34884 KB Output is correct
19 Correct 126 ms 32992 KB Output is correct
20 Correct 127 ms 33712 KB Output is correct
21 Correct 126 ms 35220 KB Output is correct
22 Correct 134 ms 35092 KB Output is correct
23 Correct 136 ms 32832 KB Output is correct
24 Correct 142 ms 33708 KB Output is correct
25 Correct 119 ms 35108 KB Output is correct
26 Correct 108 ms 32912 KB Output is correct
27 Correct 109 ms 33768 KB Output is correct
28 Correct 88 ms 35116 KB Output is correct
29 Correct 38 ms 29664 KB Output is correct
30 Correct 44 ms 32320 KB Output is correct
31 Correct 42 ms 30228 KB Output is correct
32 Correct 42 ms 32096 KB Output is correct
33 Correct 42 ms 32288 KB Output is correct
34 Correct 43 ms 32372 KB Output is correct
35 Correct 1 ms 300 KB Output is correct
36 Correct 130 ms 32108 KB Output is correct
37 Correct 128 ms 34908 KB Output is correct
38 Correct 122 ms 33316 KB Output is correct
39 Correct 125 ms 35272 KB Output is correct
40 Correct 128 ms 35220 KB Output is correct
41 Correct 51 ms 32280 KB Output is correct
42 Correct 114 ms 33220 KB Output is correct
43 Correct 116 ms 35144 KB Output is correct
44 Correct 145 ms 35140 KB Output is correct
45 Correct 98 ms 33164 KB Output is correct
46 Correct 84 ms 35100 KB Output is correct
47 Correct 86 ms 35144 KB Output is correct