Submission #1023847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023847		kunzaZa183	Mutating DNA (IOI21_dna)	C++17	100 / 100	40 ms	6424 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100001;
int at[maxn], ac[maxn], ca[maxn], ct[maxn], ta[maxn], tc[maxn];

void init(string a, string b) {
  for (int i = 0; i < a.size(); i++) {
    string x;
    x.push_back(a[i]);
    x.push_back(b[i]);
    if (x == "AT")
      at[i + 1] = 1;
    else if (x == "AC")
      ac[i + 1] = 1;
    else if (x == "CA")
      ca[i + 1] = 1;
    else if (x == "CT")
      ct[i + 1] = 1;
    else if (x == "TA")
      ta[i + 1] = 1;
    else if (x == "TC")
      tc[i + 1] = 1;
  }
  int len = a.size();
  auto psum = [len](int arr[]) {
    for (int i = 1; i <= len; i++) arr[i] += arr[i - 1];
  };
  psum(at);
  psum(ac);
  psum(ca);
  psum(ct);
  psum(ta);
  psum(tc);
}

int get_distance(int x, int y) {
  auto qry = [x, y](int arr[]) { return arr[y + 1] - arr[x]; };
  int ati = qry(at), aci = qry(ac), cai = qry(ca), cti = qry(ct), tai = qry(ta),
      tci = qry(tc);

  int ans = 0;
  int val = min(ati, tai);
  ans += val;
  ati -= val, tai -= val;
  val = min(aci, cai);
  ans += val;
  aci -= val, cai -= val;
  val = min(cti, tci);
  ans += val;
  cti -= val, tci -= val;

  val = min({aci, cti, tai});
  aci -= val, cti -= val, tai -= val;
  ans += 2 * val;

  val = min({cai, ati, tci});
  cai -= val, ati -= val, tci -= val;
  ans += 2 * val;

  if (ati > 0 || aci > 0 || cai > 0 || cti > 0 || tai > 0 || tci > 0) return -1;
  return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:9:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |   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