Submission #1142376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142376		vyaduct	Mutating DNA (IOI21_dna)	C++20	35 / 100	38 ms	4876 KiB

dna

#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

#define DEBUG true
#define DBG(x) cout << #x << " = " << x << ";\n";

const int N = 100001;
int AT[N], TA[N], AC[N], CA[N], CT[N], TC[N];

void init(string a, string b) {
  int n = (int)a.size();
  for (int i=0;i<n;i++){
    AT[i] = (i == 0 ? 0 : AT[i-1]) + (a[i] == 'A' && b[i] == 'T');
    TA[i] = (i == 0 ? 0 : TA[i-1]) + (a[i] == 'T' && b[i] == 'A');
    AC[i] = (i == 0 ? 0 : AC[i-1]) + (a[i] == 'A' && b[i] == 'C');
    CA[i] = (i == 0 ? 0 : CA[i-1]) + (a[i] == 'C' && b[i] == 'A');
    TC[i] = (i == 0 ? 0 : TC[i-1]) + (a[i] == 'T' && b[i] == 'C');
    CT[i] = (i == 0 ? 0 : CT[i-1]) + (a[i] == 'C' && b[i] == 'T');
  }
}

int get_distance(int x, int y) {
  int at = AT[y] - (x==0?0:AT[x-1]);
  int ta = TA[y] - (x==0?0:TA[x-1]);
  int ac = AC[y] - (x==0?0:AC[x-1]);
  int ca = CA[y] - (x==0?0:CA[x-1]);
  int tc = TC[y] - (x==0?0:TC[x-1]);
  int ct = CT[y] - (x==0?0:CT[x-1]);

  int ans = 0;
  ans += min(at, ta);
  ans += min(ac, ca);
  ans += min(ct, tc);
  int m1 = min(at, ta), m2 = min(ac,ca), m3 = min(ct, tc);
  at -= m1, ta -= m1; 
  ac -= m2, ca -= m2; 
  tc -= m3, ta -= m3; 
  int fa=at-ta+ac-ca;
  int fc=ct-tc+ca-ac;
  int ft=ta-at+tc-ct;
  int sum=ac+ca+at+ta+tc+ct;
  if (fa != 0 || fc != 0 || ft != 0) return -1;
	return ans + (sum/3)*2;
}

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