Submission #1118944

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118944		mannshah1211	Mutating DNA (IOI21_dna)	C++17	100 / 100	96 ms	34524 KiB

dna

/**
 *    author: tourist
 *    created:
**/
#include "dna.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int value(char c) {
  if (c == 'A') {
    return 0;
  }
  if (c == 'C') {
    return 1;
  }
  if (c == 'T') {
    return 2;
  }
}

vector<vector<int>> pa, pb;
vector<vector<vector<int>>> diff;

void init(string a, string b) {
  a = '$' + a; b = '$' + b;
  pa.resize(a.length() + 1);
  pb.resize(b.length() + 1);
  for (int i = 0; i <= a.length(); i++) {
    pa[i].resize(3);
  }
  for (int i = 0; i <= b.length(); i++) {
    pb[i].resize(3);
  }
  for (int i = 1; i <= a.length(); i++) {
    for (int j = 0; j < 3; j++) {
      pa[i][j] = pa[i - 1][j];
    }
    pa[i][value(a[i])]++;
  }
  for (int i = 1; i <= b.length(); i++) {
    for (int j = 0; j < 3; j++) {
      pb[i][j] = pb[i - 1][j];
    }
    pb[i][value(b[i])]++;
  }
  diff.resize(a.length() + 1);
  for (int i = 0; i <= a.length(); i++) {
    diff[i].resize(3);
    for (int j = 0; j < 3; j++) {
      diff[i][j].resize(3);
    }
  }
  for (int i = 1; i <= a.length(); i++) {
    for (int j = 0; j < 3; j++) {
      for (int k = 0; k < 3; k++) {
        diff[i][j][k] = diff[i - 1][j][k];
      }
    }
    diff[i][value(a[i])][value(b[i])]++;
  }
}

int get_distance(int x, int y) {
  x++; y++;
  for (int i = 0; i < 3; i++) {
    if (pa[y][i] - pa[x - 1][i] != pb[y][i] - pb[x - 1][i]) {
      return -1;
    }
  }
  int ans = 0, mn = 1e9;
  for (int i = 0; i < 3; i++) {
    for (int j = i + 1; j < 3; j++) {
      ans += min(diff[y][i][j] - diff[x - 1][i][j], diff[y][j][i] - diff[x - 1][j][i]);
      mn = min(mn, abs((diff[y][i][j] - diff[x - 1][i][j]) - (diff[y][j][i] - diff[x - 1][j][i])));
    }
  }
  ans += 2 * mn;
  return ans;
} 

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:35:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |   for (int i = 0; i <= a.length(); i++) {
      |                   ~~^~~~~~~~~~~~~
dna.cpp:38:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for (int i = 0; i <= b.length(); i++) {
      |                   ~~^~~~~~~~~~~~~
dna.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int i = 1; i <= a.length(); i++) {
      |                   ~~^~~~~~~~~~~~~
dna.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 1; i <= b.length(); i++) {
      |                   ~~^~~~~~~~~~~~~
dna.cpp:54:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   for (int i = 0; i <= a.length(); i++) {
      |                   ~~^~~~~~~~~~~~~
dna.cpp:60:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for (int i = 1; i <= a.length(); i++) {
      |                   ~~^~~~~~~~~~~~~
dna.cpp: In function 'int value(char)':
dna.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

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