Submission #1230708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230708		rxlfd314	Mutating DNA (IOI21_dna)	C++20	100 / 100	39 ms	4880 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 100005;
int psum[mxN][6];
map<array<char, 2>, int> mm = {{{'A', 'T'}, 0}, {{'T', 'A'}, 1}, {{'A', 'C'}, 2}, {{'C', 'A'}, 3}, {{'C', 'T'}, 4}, {{'T', 'C'}, 5}};

void init(const string A, const string B) {
  const int N = size(A);
  FOR(i, 0, N-1) {
    FOR(j, 0, 5)
      psum[i+1][j] = psum[i][j];
    if (A[i] != B[i])
      psum[i+1][mm[{A[i], B[i]}]]++;
  }
}

int get_distance(const int x, const int y) {
  vt<int> cnt(6);
  FOR(i, 0, 5)
    cnt[i] = psum[y+1][i] - psum[x][i];
  int ans = 0;
  REP(i, 0, 4, 2) {
    const int v = min(cnt[i], cnt[i+1]);
    ans += v;
    cnt[i] -= v;
    cnt[i+1] -= v;
  }
  vt<int> pos;
  FOR(i, 0, 5)
    if (cnt[i])
      pos.push_back(i);
  if (!size(pos))
    return ans;
  if (size(pos) != 3 || pos != vt<int>{0, 3, 5} && pos != vt<int>{1, 2, 4} || cnt[pos[0]] != cnt[pos[1]] || cnt[pos[0]] != cnt[pos[2]])
    return -1;
  return ans + cnt[pos[0]] * 2;
}

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