Submission #988383

#	Time	Username	Problem	Language	Result	Execution time	Memory
988383		kachim2	Mutating DNA (IOI21_dna)	C++17	100 / 100	49 ms	7184 KiB

dna

#include "dna.h"
#include <algorithm>
#include <vector>
#include <array>

#include <iostream>
std::array<std::array<std::vector<int>, 3>, 3> aaa;
std::array<int, 256> chtoi = {};
void init(std::string a, std::string b) {
  chtoi['A'] = 0;
  chtoi['T'] = 1;
  chtoi['C'] = 2;
  for (auto &i : aaa) {
    for (auto &j : i) {
      j.resize(a.size()+1);
      std::fill(j.begin(), j.end(), 0);
    }
  }
  for (int i = 0; i < a.size(); i++) {
      for (auto &A : aaa) {
    for (auto &j : A) {
      j[i+1] = j[i];
    }
      }
      aaa[chtoi[a[i]]][chtoi[b[i]]][i+1] ++;
  }
}

int get_distance(int x, int y) {
  int ret = 0;
  std::array<std::array<int, 3>, 3> bbb;
  
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if(j!=i)
        bbb[i][j] = aaa[i][j][y + 1] - aaa[i][j][x];
      else
	bbb[i][j] = 0;
    }
  }
  for (int i = 0; i < 3; i++) {
    for (int j = i+1; j < 3; j++) {
      const int x = std::min(bbb[i][j], bbb[j][i]);
      ret+=x;
      bbb[i][j] -= x;
      bbb[j][i] -=x;
    }
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if(i!=j){
        const int x = std::min(bbb[i][j], bbb[j][i]);
	ret+=x;
      bbb[i][j] -= x;
      bbb[j][i] -= x;
      
      ret+=bbb[i][j];
      bbb[i][3-i-j]+=bbb[i][j];
      bbb[j][3 - i - j] -= bbb[i][j];
      bbb[i][j] = 0;
      }
    }
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if(i!=j){
        const int x = std::min(bbb[i][j], bbb[j][i]);
	ret+=x;
      bbb[i][j] -= x;
      bbb[j][i] -= x;
      
      ret+=bbb[i][j];
      bbb[i][3-i-j]+=bbb[i][j];
      bbb[j][3 - i - j] -= bbb[i][j];
      bbb[i][j] = 0;
      }
    }
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if(bbb[i][j] != 0) return -1;
    }
  }
  
  return ret;
}

Compilation message (stderr)

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