Submission #764634

#	Time	Username	Problem	Language	Result	Execution time	Memory
764634		ind1v	Mutating DNA (IOI21_dna)	C++17	100 / 100	35 ms	9788 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

const int N = 100005;

int n;
int aca[N], acc[N], act[N];
int bca[N], bcc[N], bct[N];
int cnt[N][3][3];

int comp(int x) {
  if (x == 0) {
    return 0;
  }
  if (x == 2) {
    return 1;
  }
  if (x == 19) {
    return 2;
  }
}

void init(string a, string b) {
  n = a.size();
  a = '#' + a;
  b = '#' + b;
  for (int i = 1; i <= n; i++) {
    a[i] -= 'A' - 'a';
    b[i] -= 'A' - 'a';
  }
  for (int i = 1; i <= n; i++) {
    if (a[i] == 'a') {
      aca[i] = 1;
    } else if (a[i] == 'c') {
      acc[i] = 1;
    } else {
      act[i] = 1;
    }
    if (b[i] == 'a') {
      bca[i] = 1;
    } else if (b[i] == 'c') {
      bcc[i] = 1;
    } else {
      bct[i] = 1;
    }
    cnt[i][comp(a[i] - 'a')][comp(b[i] - 'a')] = 1;
  }
  partial_sum(aca + 1, aca + n + 1, aca + 1);
  partial_sum(acc + 1, acc + n + 1, acc + 1);
  partial_sum(act + 1, act + n + 1, act + 1);
  partial_sum(bca + 1, bca + n + 1, bca + 1);
  partial_sum(bcc + 1, bcc + n + 1, bcc + 1);
  partial_sum(bct + 1, bct + n + 1, bct + 1);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        cnt[i][j][k] += cnt[i - 1][j][k];
      }
    }
  }
}

int get_distance(int x, int y) {
  ++x; ++y;
  int tot_a = aca[y] - aca[x - 1] - (bca[y] - bca[x - 1]);
  int tot_c = acc[y] - acc[x - 1] - (bcc[y] - bcc[x - 1]);
  int tot_t = act[y] - act[x - 1] - (bct[y] - bct[x - 1]);
  if (tot_a != 0 || tot_c != 0 || tot_t != 0) {
    return -1;
  }
  int cnt_ac = cnt[y][0][1] - cnt[x - 1][0][1];
  int cnt_at = cnt[y][0][2] - cnt[x - 1][0][2];
  int cnt_ca = cnt[y][1][0] - cnt[x - 1][1][0];
  int cnt_ct = cnt[y][1][2] - cnt[x - 1][1][2];
  int cnt_ta = cnt[y][2][0] - cnt[x - 1][2][0];
  int cnt_tc = cnt[y][2][1] - cnt[x - 1][2][1];
  int ans = 0;
  int mn = min(cnt_ac, cnt_ca);
  ans += mn;
  cnt_ac -= mn;
  cnt_ca -= mn;
  mn = min(cnt_at, cnt_ta);
  ans += mn;
  cnt_at -= mn;
  cnt_ta -= mn;
  mn = min(cnt_ct, cnt_tc);
  ans += mn;
  cnt_ct -= mn;
  cnt_tc -= mn;
  ans += (cnt_ac + cnt_at + cnt_ca + cnt_ct + cnt_ta + cnt_tc) / 3 * 2;
  return ans;
}

Compilation message (stderr)

dna.cpp: In function 'int comp(int)':
dna.cpp:23:1: warning: control reaches end of non-void function [-Wreturn-type]
   23 | }
      | ^

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