Submission #442117

#	Time	Username	Problem	Language	Result	Execution time	Memory
442117		SorahISA	Mutating DNA (IOI21_dna)	C++17	0 / 100	83 ms	5228 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, BIT[maxn];
string A, B;
vector<tuple<int, int, int>> cntA, cntB;

int trans[256];

void bit_add(int idx, int val) {
    ++idx; /// make sure index \ne 0 -> shift BIT right by 1
    while (idx < maxn) BIT[idx] += val, idx += idx & -idx;
}

int bit_sum(int idxL, int idxR, int ans = 0) {
    ++idxR; /// make sure idxL \ne 0 -> shift BIT right by 1
    while (idxR) ans += BIT[idxR], idxR -= idxR & -idxR;
    while (idxL) ans -= BIT[idxL], idxL -= idxL & -idxL;
    return ans;
}

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

} /// 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['A'] = 0, trans['T'] = 1, trans['C'] = 2;
    for (int i = 0; i < N; ++i) {
        if (i) cntA[i] = cntA[i-1], cntB[i] = cntB[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;
    }
}

/*

CAACTATCT
ATTCTCACA

CAACTATCT
ACACTATCT +1
ATCACATCT +3
ATTCACACT +4
ATTCACACT +0
ATTCTACAC +4
ATTCTCAAC +1
ATTCTCAAC +0
ATTCTCACA +1
ATTCTCACA +0

ATTCTCACA

*/

int get_distance(int L, int R) {
    if (!is_same_dna(L, R)) return -1;
    
    /// brute force ///
    
    int ans = 0;
    
    deque<int> place[3]; /// ATC
    for (int i = L, tok = L; i <= R; ++i) {
        while (place[trans[B[i]]].empty()) {
            place[trans[A[tok]]].eb(tok), ++tok;
        }
        int chosen_place = place[trans[B[i]]].front();
        // cerr << chosen_place << "\n";
        ans += (i - L) - bit_sum(L, chosen_place);
        bit_add(chosen_place, 1);
        place[trans[B[i]]].pf();
    }
    
    for (int i = L; i <= R; ++i) bit_add(i, -1);
    
    return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:69:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   69 |         if (A[i] == 'A') ++AA; if (A[i] == 'T') ++AT; if (A[i] == 'C') ++AC;
      |         ^~
dna.cpp:69:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   69 |         if (A[i] == 'A') ++AA; if (A[i] == 'T') ++AT; if (A[i] == 'C') ++AC;
      |                                ^~
dna.cpp:70:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   70 |         if (B[i] == 'A') ++BA; if (B[i] == 'T') ++BT; if (B[i] == 'C') ++BC;
      |         ^~
dna.cpp:70:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   70 |         if (B[i] == 'A') ++BA; if (B[i] == 'T') ++BT; if (B[i] == 'C') ++BC;
      |                                ^~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:103:32: warning: array subscript has type 'char' [-Wchar-subscripts]
  103 |         while (place[trans[B[i]]].empty()) {
      |                                ^
dna.cpp:104:31: warning: array subscript has type 'char' [-Wchar-subscripts]
  104 |             place[trans[A[tok]]].eb(tok), ++tok;
      |                               ^
dna.cpp:106:44: warning: array subscript has type 'char' [-Wchar-subscripts]
  106 |         int chosen_place = place[trans[B[i]]].front();
      |                                            ^
dna.cpp:110:25: warning: array subscript has type 'char' [-Wchar-subscripts]
  110 |         place[trans[B[i]]].pf();
      |                         ^

• Subtask 1: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16