oj.uz

Submission #542045

# Submission time Handle Problem Language Result Execution time Memory
542045 2022-03-25T08:50:26 Z Vladth11 Mutating DNA (IOI21_dna) C++17
100 / 100
 230 ms 17960 KB 
#include <bits/stdc++.h>
#include "dna.h"
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 1000001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 1000000;
const ll nr_of_bits = 16;

struct mat{
    int wrong[3][3];
    void clear(){
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++)
                wrong[i][j] = 0;
        }
    }
};

class AINT {
    public:
    mat aint[4 * NMAX];
    mat combine(mat a, mat b) {
        mat sol;
        sol.clear();
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < 3; j++) {
                sol.wrong[i][j] = a.wrong[i][j] + b.wrong[i][j];
            }
        }
        return sol;
    }
    void update(int node, int st, int dr, int poz, int a, int b) {
        aint[node].wrong[a][b]++;
        if(st == dr) {
            return;
        }
        int mid = (st + dr) / 2;
        if(poz <= mid)
            update(node * 2, st, mid, poz, a, b);
        else
            update(node * 2 + 1, mid + 1, dr, poz, a, b);
    }
    mat query(int node, int st, int dr, int a, int b) {
        if(a <= st && dr <= b) {
            return aint[node];
        }
        int mid = (st + dr) / 2;
        mat sol;
        sol.clear();
        if(a <= mid)
            sol = combine(sol, query(node * 2, st, mid, a, b));
        if(b > mid)
            sol = combine(sol, query(node * 2 + 1, mid + 1, dr, a, b));
        return sol;
    }
}st;

int n;

int getCode(char c){
    if(c == 'A')
        return 0;
    else if(c == 'C')
        return 1;
    return 2;
}

void init(std::string a, std::string b) {
    n = a.size();
    for(int i = 0; i < 4 * NMAX; i++)
        st.aint[i].clear();
    for(int i = 0; i < a.size(); i++){
        int codA = getCode(a[i]);
        int codB = getCode(b[i]);
        if(codA != codB)
            st.update(1, 1, n, i + 1, codA, codB);
    }
}

int get_distance(int x, int y) {
    x++;
    y++;
    mat my = st.query(1, 1, n, x, y);
    for(int i = 0; i < 3; i++){
        int s = 0;
        for(int j = 0; j < 3; j++){
            s += my.wrong[i][j];
        }
        for(int j = 0; j < 3; j++){
            s -= my.wrong[j][i];
        }
        if(s != 0){
            return -1;
        }
    }
    int cnt = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            int minim = min(my.wrong[j][i], my.wrong[i][j]);
            my.wrong[j][i] -= minim;
            my.wrong[i][j] -= minim;
            cnt += minim;
        }
    }
    int s = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
            s += my.wrong[i][j];
        }
    }
    s /= 3;
    s *= 2;
    cnt += s;
    return cnt;
}

Compilation message

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:81:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int i = 0; i < a.size(); i++){
      |                    ~~^~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 17528 KB Output is correct
2 Correct 103 ms 17560 KB Output is correct
3 Correct 89 ms 17540 KB Output is correct
4 Correct 91 ms 17568 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 8 ms 14384 KB Output is correct
7 Correct 8 ms 14304 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14388 KB Output is correct
2 Correct 9 ms 14320 KB Output is correct
3 Correct 7 ms 14296 KB Output is correct
4 Correct 13 ms 15084 KB Output is correct
5 Correct 13 ms 15172 KB Output is correct
6 Correct 12 ms 15080 KB Output is correct
7 Correct 12 ms 15060 KB Output is correct
8 Correct 14 ms 15164 KB Output is correct
9 Correct 11 ms 15060 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14388 KB Output is correct
2 Correct 9 ms 14320 KB Output is correct
3 Correct 7 ms 14296 KB Output is correct
4 Correct 13 ms 15084 KB Output is correct
5 Correct 13 ms 15172 KB Output is correct
6 Correct 12 ms 15080 KB Output is correct
7 Correct 12 ms 15060 KB Output is correct
8 Correct 14 ms 15164 KB Output is correct
9 Correct 11 ms 15060 KB Output is correct
10 Correct 106 ms 17676 KB Output is correct
11 Correct 107 ms 17556 KB Output is correct
12 Correct 154 ms 17880 KB Output is correct
13 Correct 160 ms 17916 KB Output is correct
14 Correct 230 ms 17908 KB Output is correct
15 Correct 156 ms 17800 KB Output is correct
16 Correct 158 ms 17788 KB Output is correct
17 Correct 181 ms 17824 KB Output is correct
18 Correct 149 ms 17904 KB Output is correct
19 Correct 166 ms 17816 KB Output is correct
20 Correct 152 ms 17808 KB Output is correct
21 Correct 156 ms 17836 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14388 KB Output is correct
2 Correct 9 ms 14320 KB Output is correct
3 Correct 7 ms 14296 KB Output is correct
4 Correct 13 ms 15084 KB Output is correct
5 Correct 13 ms 15172 KB Output is correct
6 Correct 12 ms 15080 KB Output is correct
7 Correct 12 ms 15060 KB Output is correct
8 Correct 14 ms 15164 KB Output is correct
9 Correct 11 ms 15060 KB Output is correct
10 Correct 14 ms 15072 KB Output is correct
11 Correct 14 ms 15164 KB Output is correct
12 Correct 17 ms 15060 KB Output is correct
13 Correct 15 ms 15060 KB Output is correct
14 Correct 13 ms 15168 KB Output is correct
15 Correct 13 ms 15120 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 17528 KB Output is correct
2 Correct 103 ms 17560 KB Output is correct
3 Correct 89 ms 17540 KB Output is correct
4 Correct 91 ms 17568 KB Output is correct
5 Correct 8 ms 14388 KB Output is correct
6 Correct 8 ms 14384 KB Output is correct
7 Correct 8 ms 14304 KB Output is correct
8 Correct 8 ms 14388 KB Output is correct
9 Correct 9 ms 14320 KB Output is correct
10 Correct 7 ms 14296 KB Output is correct
11 Correct 13 ms 15084 KB Output is correct
12 Correct 13 ms 15172 KB Output is correct
13 Correct 12 ms 15080 KB Output is correct
14 Correct 12 ms 15060 KB Output is correct
15 Correct 14 ms 15164 KB Output is correct
16 Correct 11 ms 15060 KB Output is correct
17 Correct 106 ms 17676 KB Output is correct
18 Correct 107 ms 17556 KB Output is correct
19 Correct 154 ms 17880 KB Output is correct
20 Correct 160 ms 17916 KB Output is correct
21 Correct 230 ms 17908 KB Output is correct
22 Correct 156 ms 17800 KB Output is correct
23 Correct 158 ms 17788 KB Output is correct
24 Correct 181 ms 17824 KB Output is correct
25 Correct 149 ms 17904 KB Output is correct
26 Correct 166 ms 17816 KB Output is correct
27 Correct 152 ms 17808 KB Output is correct
28 Correct 156 ms 17836 KB Output is correct
29 Correct 14 ms 15072 KB Output is correct
30 Correct 14 ms 15164 KB Output is correct
31 Correct 17 ms 15060 KB Output is correct
32 Correct 15 ms 15060 KB Output is correct
33 Correct 13 ms 15168 KB Output is correct
34 Correct 13 ms 15120 KB Output is correct
35 Correct 7 ms 14292 KB Output is correct
36 Correct 91 ms 17488 KB Output is correct
37 Correct 103 ms 17564 KB Output is correct
38 Correct 179 ms 17904 KB Output is correct
39 Correct 165 ms 17940 KB Output is correct
40 Correct 187 ms 17940 KB Output is correct
41 Correct 11 ms 15168 KB Output is correct
42 Correct 150 ms 17960 KB Output is correct
43 Correct 150 ms 17956 KB Output is correct
44 Correct 171 ms 17856 KB Output is correct
45 Correct 150 ms 17800 KB Output is correct
46 Correct 163 ms 17844 KB Output is correct
47 Correct 170 ms 17948 KB Output is correct