Submission #437071

#	Time	Username	Problem	Language	Result	Execution time	Memory
437071		monsoon	Mutating DNA (IOI21_dna)	C++17	0 / 100	45 ms	5916 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];

  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 = 0;
  REP(a,3) REP(b,3) sum += in.cnt[a][b];

  if (sum % 3 != 0) return -1;
  ans += sum/3 * 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: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16