oj.uz

Submission #442137

# Submission time Handle Problem Language Result Execution time Memory
442137 2021-07-07T07:56:24 Z SorahISA Mutating DNA (IOI21_dna) C++17
100 / 100
 71 ms 8856 KB 
#include "dna.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)

namespace {

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1 << 17;

int N;
string A, B;
vector<tuple<int, int, int>> cntA, cntB;
vector<array<array<int, 3>, 3>> _trans;

int to_int[256];

inline int is_same_dna(int L, int R) {
    if (L == 0) return cntA[R] == cntB[R];
    auto &[LAA, LAT, LAC] = cntA[L-1];
    auto &[LBA, LBT, LBC] = cntB[L-1];
    auto &[RAA, RAT, RAC] = cntA[R];
    auto &[RBA, RBT, RBC] = cntB[R];
    return (RAA - LAA == RBA - LBA) and
           (RAT - LAT == RBT - LBT) and
           (RAC - LAC == RBC - LBC);
}

array<array<int, 3>, 3> get_range_trans(int L, int R) {
    if (L == 0) return _trans[R];
    array<array<int, 3>, 3> tmp;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            tmp[i][j] = _trans[R][i][j] - _trans[L-1][i][j];
        }
    }
    return tmp;
}

} /// end of namespace

void init(string _A, string _B) {
    A = _A, B = _B, N = A.size();
    cntA.assign(N, {0, 0, 0}), cntB.assign(N, {0, 0, 0});
    _trans.resize(N);
    to_int['A'] = 0, to_int['T'] = 1, to_int['C'] = 2;
    for (int i = 0; i < N; ++i) {
        if (i) cntA[i] = cntA[i-1], cntB[i] = cntB[i-1], _trans[i] = _trans[i-1];
        auto &[AA, AT, AC] = cntA[i];
        auto &[BA, BT, BC] = cntB[i];
        if (A[i] == 'A') ++AA; if (A[i] == 'T') ++AT; if (A[i] == 'C') ++AC;
        if (B[i] == 'A') ++BA; if (B[i] == 'T') ++BT; if (B[i] == 'C') ++BC;
        ++_trans[i][to_int[A[i]]][to_int[B[i]]];
    }
}

int get_distance(int L, int R) {
    if (!is_same_dna(L, R)) return -1;
    
    auto trans = get_range_trans(L, R);
    
    // cerr << "Before:\n";
    // for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) cerr << trans[i][j] << " \n"[j == 2];
    
    int minAT, minTC, minCA;
    minAT = min(trans[0][1], trans[1][0]), trans[0][1] -= minAT, trans[1][0] -= minAT;
    minTC = min(trans[1][2], trans[2][1]), trans[1][2] -= minTC, trans[2][1] -= minTC;
    minCA = min(trans[2][0], trans[0][2]), trans[2][0] -= minCA, trans[0][2] -= minCA;
    
    // cerr << "After:\n";
    // for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) cerr << trans[i][j] << " \n"[j == 2];
    
    return minAT + minTC + minCA + 2 * max(trans[0][1], trans[0][2]);
}

Compilation message

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:68:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |         if (A[i] == 'A') ++AA; if (A[i] == 'T') ++AT; if (A[i] == 'C') ++AC;
      |         ^~
dna.cpp:68:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |         if (A[i] == 'A') ++AA; if (A[i] == 'T') ++AT; if (A[i] == 'C') ++AC;
      |                                ^~
dna.cpp:69:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   69 |         if (B[i] == 'A') ++BA; if (B[i] == 'T') ++BT; if (B[i] == 'C') ++BC;
      |         ^~
dna.cpp:69:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   69 |         if (B[i] == 'A') ++BA; if (B[i] == 'T') ++BT; if (B[i] == 'C') ++BC;
      |                                ^~
dna.cpp:70:32: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |         ++_trans[i][to_int[A[i]]][to_int[B[i]]];
      |                                ^
dna.cpp:70:46: warning: array subscript has type 'char' [-Wchar-subscripts]
   70 |         ++_trans[i][to_int[A[i]]][to_int[B[i]]];
      |                                              ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8132 KB Output is correct
2 Correct 44 ms 8248 KB Output is correct
3 Correct 43 ms 7704 KB Output is correct
4 Correct 45 ms 8368 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 292 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 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 7 ms 6860 KB Output is correct
5 Correct 8 ms 6860 KB Output is correct
6 Correct 6 ms 6860 KB Output is correct
7 Correct 6 ms 6476 KB Output is correct
8 Correct 9 ms 6860 KB Output is correct
9 Correct 6 ms 6860 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 7 ms 6860 KB Output is correct
5 Correct 8 ms 6860 KB Output is correct
6 Correct 6 ms 6860 KB Output is correct
7 Correct 6 ms 6476 KB Output is correct
8 Correct 9 ms 6860 KB Output is correct
9 Correct 6 ms 6860 KB Output is correct
10 Correct 43 ms 8236 KB Output is correct
11 Correct 43 ms 8260 KB Output is correct
12 Correct 44 ms 8172 KB Output is correct
13 Correct 43 ms 8344 KB Output is correct
14 Correct 47 ms 8556 KB Output is correct
15 Correct 45 ms 8512 KB Output is correct
16 Correct 60 ms 8156 KB Output is correct
17 Correct 41 ms 8260 KB Output is correct
18 Correct 41 ms 8580 KB Output is correct
19 Correct 53 ms 8164 KB Output is correct
20 Correct 40 ms 8388 KB Output is correct
21 Correct 40 ms 8640 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 7 ms 6860 KB Output is correct
5 Correct 8 ms 6860 KB Output is correct
6 Correct 6 ms 6860 KB Output is correct
7 Correct 6 ms 6476 KB Output is correct
8 Correct 9 ms 6860 KB Output is correct
9 Correct 6 ms 6860 KB Output is correct
10 Correct 7 ms 6348 KB Output is correct
11 Correct 8 ms 7116 KB Output is correct
12 Correct 7 ms 6604 KB Output is correct
13 Correct 9 ms 6984 KB Output is correct
14 Correct 9 ms 7140 KB Output is correct
15 Correct 6 ms 7116 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 8132 KB Output is correct
2 Correct 44 ms 8248 KB Output is correct
3 Correct 43 ms 7704 KB Output is correct
4 Correct 45 ms 8368 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 7 ms 6860 KB Output is correct
12 Correct 8 ms 6860 KB Output is correct
13 Correct 6 ms 6860 KB Output is correct
14 Correct 6 ms 6476 KB Output is correct
15 Correct 9 ms 6860 KB Output is correct
16 Correct 6 ms 6860 KB Output is correct
17 Correct 43 ms 8236 KB Output is correct
18 Correct 43 ms 8260 KB Output is correct
19 Correct 44 ms 8172 KB Output is correct
20 Correct 43 ms 8344 KB Output is correct
21 Correct 47 ms 8556 KB Output is correct
22 Correct 45 ms 8512 KB Output is correct
23 Correct 60 ms 8156 KB Output is correct
24 Correct 41 ms 8260 KB Output is correct
25 Correct 41 ms 8580 KB Output is correct
26 Correct 53 ms 8164 KB Output is correct
27 Correct 40 ms 8388 KB Output is correct
28 Correct 40 ms 8640 KB Output is correct
29 Correct 7 ms 6348 KB Output is correct
30 Correct 8 ms 7116 KB Output is correct
31 Correct 7 ms 6604 KB Output is correct
32 Correct 9 ms 6984 KB Output is correct
33 Correct 9 ms 7140 KB Output is correct
34 Correct 6 ms 7116 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 46 ms 7876 KB Output is correct
37 Correct 47 ms 8456 KB Output is correct
38 Correct 48 ms 8432 KB Output is correct
39 Correct 61 ms 8856 KB Output is correct
40 Correct 71 ms 8844 KB Output is correct
41 Correct 7 ms 7116 KB Output is correct
42 Correct 44 ms 8440 KB Output is correct
43 Correct 66 ms 8784 KB Output is correct
44 Correct 55 ms 8848 KB Output is correct
45 Correct 49 ms 8516 KB Output is correct
46 Correct 41 ms 8824 KB Output is correct
47 Correct 41 ms 8816 KB Output is correct