Submission #705044

#	Time	Username	Problem	Language	Result	Execution time	Memory
705044		jakobrs	Mutating DNA (IOI21_dna)	C++17	100 / 100	68 ms	16460 KiB

dna

#include <iostream>
#include <vector>

struct Count {
  int a1, a2;
  int t1, t2;
  int c1, c2;

  int at, ta;
  int ac, ca;
  int tc, ct;

  Count()
      : a1(0),
        a2(0),
        t1(0),
        t2(0),
        c1(0),
        c2(0),
        at(0),
        ta(0),
        ac(0),
        ca(0),
        tc(0),
        ct(0) {}

  Count operator+(const Count &rhs) const {
    Count res = *this;
    res += rhs;
    return res;
  }

  void operator+=(const Count &rhs) {
    a1 += rhs.a1;
    a2 += rhs.a2;
    t1 += rhs.t1;
    t2 += rhs.t2;
    c1 += rhs.c1;
    c2 += rhs.c2;

    at += rhs.at;
    ta += rhs.ta;
    ac += rhs.ac;
    ca += rhs.ca;
    tc += rhs.tc;
    ct += rhs.ct;
  }
};

struct SegmentTree {
  std::vector<Count> values;
  int offset;

  SegmentTree(int n) {
    offset = 1;
    while (offset < n) offset *= 2;

    values = std::vector<Count>(2 * offset);
  }

  void update(int idx, Count count_diff) {
    idx += offset;
    while (idx > 0) {
      values[idx] += count_diff;
      idx /= 2;
    }
  }

  Count query(int l, int r) const {
    Count count;

    l += offset;
    r += offset;
    while (l < r) {
      if (l & 1) count += values[l++];
      if (r & 1) count += values[--r];

      l /= 2;
      r /= 2;
    }

    return count;
  }
};

std::string a, b;
SegmentTree st(0);

void init(std::string A, std::string B) {
  a = A;
  b = B;

  st = SegmentTree(A.size());
  for (int i = 0; i < A.size(); i++) {
    Count diff;
    if (A[i] == 'A') diff.a1 += 1;
    if (B[i] == 'A') diff.a2 += 1;
    if (A[i] == 'T') diff.t1 += 1;
    if (B[i] == 'T') diff.t2 += 1;
    if (A[i] == 'C') diff.c1 += 1;
    if (B[i] == 'C') diff.c2 += 1;
    if (A[i] == 'A' && B[i] == 'T') diff.at += 1;
    if (A[i] == 'T' && B[i] == 'A') diff.ta += 1;
    if (A[i] == 'A' && B[i] == 'C') diff.ac += 1;
    if (A[i] == 'C' && B[i] == 'A') diff.ca += 1;
    if (A[i] == 'T' && B[i] == 'C') diff.tc += 1;
    if (A[i] == 'C' && B[i] == 'T') diff.ct += 1;
    st.update(i, diff);
  }
}

int get_distance(int x, int y) {
  y += 1;

  Count count = st.query(x, y);

  if (count.a1 != count.a2 || count.t1 != count.t2 || count.c1 != count.c2) {
    return -1;
  }

  // std::cout << count.at << ' ' << count.ta << ' ' << count.ac << ' ' << count.ca << ' ' << count.tc << ' ' << count.ct << '\n';

  int at_pairs = std::min(count.at, count.ta);
  int ac_pairs = std::min(count.ac, count.ca);
  int tc_pairs = std::min(count.tc, count.ct);

  int total = at_pairs + ac_pairs + tc_pairs;

  count.at -= at_pairs;
  count.ta -= at_pairs;
  count.ac -= ac_pairs;
  count.ca -= ac_pairs;
  count.tc -= tc_pairs;
  count.ct -= tc_pairs;

  // std::cout << count.at << ' ' << count.ta << ' ' << count.ac << ' ' << count.ca << ' ' << count.tc << ' ' << count.ct << '\n';

  return total + std::max(count.at, count.ta) * 2;
}

Compilation message (stderr)

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

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