Submission #1159403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1159403		dombly	Mutating DNA (IOI21_dna)	C++20	100 / 100	37 ms	8456 KiB

dna

#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

const int N = 1e5 + 10;

int pref[N][3][3],p[N][3][2];

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

void init(string a, string b) {
  int n = (int)a.size();
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < 3; j++) {
      int coef = (i > 0 ? p[i - 1][j][0] : 0);
      p[i][j][0] = coef + (Code(a[i]) == j);
      coef = (i > 0 ? p[i - 1][j][1] : 0);
      p[i][j][1] = coef + (Code(b[i]) == j);
    }
    for(int j = 0; j < 3; j++) {
      for(int k = 0; k < 3; k++) {
        int c = (i > 0 ? pref[i - 1][j][k] : 0);
        pref[i][j][k] =  c + (Code(a[i]) == j && Code(b[i]) == k);
      }
    }
  }
}

bool Get(int l,int r,int f) {
  int L = (l > 0 ? p[l - 1][f][0] : 0);
  int L2 = (l > 0 ? p[l - 1][f][1] : 0);
  return (p[r][f][0] - L == p[r][f][1] - L2);
}

int get_distance(int x, int y) {
  for(int i = 0; i < 3; i++) if(!Get(x,y,i)) return -1;
  int ans = 0;
  vector<vector<int>> a(3,vector<int>(3));
  for(int i = 0; i < 3; i++) {
    for(int j = 0; j < 3; j++) {
      a[i][j] = pref[y][i][j] - (x > 0 ?  pref[x - 1][i][j] : 0);
    }
  }
  int g = 0;
  for(int i = 0; i < 3; i++) {
    for(int j = i + 1; j < 3; j++) {
      int mn = min(a[i][j],a[j][i]);
      ans += mn;
      a[i][j] -= mn;
      a[j][i] -= mn;
      g += a[i][j] + a[j][i];
    }
  }
  int f = 1e9;
  for(int i = 0; i < 3; i++) {
    int sum = 0;
    for(int j = 0; j < 3; j++) if(i != j) sum += a[j][i];
    f = min(f,sum + (g - sum ) / 2);

  }
	return ans + f;
}
/*
6 3
ATACAT
ACTATA
1 3
4 5
3 5


2
1
-1
*/

Compilation message (stderr)

dna.cpp: In function 'int Code(char)':
dna.cpp:14:1: warning: control reaches end of non-void function [-Wreturn-type]
   14 | }
      | ^

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