제출 #442137

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442137		SorahISA	DNA 돌연변이 (IOI21_dna)	C++17	100 / 100	71 ms	8856 KiB

dna

#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]);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 21
• Subtask 2: 22 / 22
• Subtask 3: 13 / 13
• Subtask 4: 28 / 28
• Subtask 5: 16 / 16