Submission #1142372

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142372		vyaduct	Mutating DNA (IOI21_dna)	C++20	0 / 100	19 ms	4608 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;
  at -= min(at, ta), ta -= min(at, ta); ans += min(at, ta);
  ac -= min(ac, ca), ca -= min(ac, ca); ans += min(ac, ca);
  tc -= min(ct, tc), ta -= min(ct, tc); ans += min(ct, tc);

  while(at>0 || ta>0 || ac>0 || ca>0 || tc>0 || ct>0){
    if (at>0) at--;
    if (ta>0) ta--;
    if (ac>0) ac--;
    if (ca>0) ca--;
    if (tc>0) tc--;
    if (ct>0) ct--;
    ans += 2;
  }
  int cnt = (at>0) + (ta>0) + (ac>0) + (ca>0) + (tc>0) + (ct>0);
  if (cnt != 0) return -1;
	return ans;
}

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