Submission #437074

#	Time	Username	Problem	Language	Result	Execution time	Memory
437074		monsoon	Mutating DNA (IOI21_dna)	C++17	100 / 100	44 ms	6340 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
#define REP(i,n) for(int i=0;i<(n);++i)
typedef long long ll;

string A, B;
int n;
int code[256];

struct info {
  int cnt[3][3];
  info() {
    REP(a,3) REP(b,3) cnt[a][b] = 0;
  }
};
vector<info> pref;


void init(string A, string B) {
  code['A'] = 0;
  code['C'] = 1;
  code['T'] = 2;

  ::A = A;
  ::B = B;
  n = A.size();
  pref.resize(n+1);

  REP(i,n) {
    REP(a,3) REP(b,3) pref[i+1].cnt[a][b] = pref[i].cnt[a][b];
    pref[i+1].cnt[code[A[i]]][code[B[i]]]++;
  }
}

int get_distance(int x, int y) {
  info in;
  REP(a,3) REP(b,3) in.cnt[a][b] = pref[y+1].cnt[a][b] - pref[x].cnt[a][b];
  REP(a,3) in.cnt[a][a] = 0;

  int ans = 0;
  REP(a,3) REP(b,a) {
    int c = min(in.cnt[a][b], in.cnt[b][a]);
    ans += c;
    in.cnt[a][b] -= c;
    in.cnt[b][a] -= c;
  }

  int sum[3][2];
  REP(a,3) REP(w,2) sum[a][w] = 0;
  REP(a,3) REP(b,3) {
    sum[a][0] += in.cnt[a][b];
    sum[b][1] += in.cnt[a][b];
  }
  REP(a,3) if (sum[a][0] != sum[a][1]) return -1;

  ans += sum[0][0] * 2;

  return ans;
}

Compilation message (stderr)

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:32:28: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |     pref[i+1].cnt[code[A[i]]][code[B[i]]]++;
      |                            ^
dna.cpp:32:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   32 |     pref[i+1].cnt[code[A[i]]][code[B[i]]]++;
      |                                        ^

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