Submission #593479

#	Time	Username	Problem	Language	Result	Execution time	Memory
593479		Pety	Mutating DNA (IOI21_dna)	C++17	22 / 100	1580 ms	4244 KiB

dna

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int INF = 1e9;
const int MOD = 1e9 + 7;

int n, p1[100002], p2[100002];

void init (string a, string b) {
  n = a.size();
  map<char, int>mp;
  mp['A'] = 1;
  mp['C'] = 2;
  mp['T'] = 3;
  for (int i = 1; i <= n; i++) {
    p1[i] = mp[a[i - 1]];
    p2[i] = mp[b[i - 1]];
  }
}

int get_distance (int x, int y) {
  x++;y++;
  int cnt[4][4], lol[4];
  memset(cnt, 0, sizeof(cnt));
  memset(lol, 0, sizeof(lol));

  for (int i = x; i <= y; i++) {
    lol[p1[i]]--;
    lol[p2[i]]++;
    cnt[p1[i]][p2[i]]++;
  }
  if (lol[1] != 0 || lol[2] != 0 || lol[3] != 0)
    return -1;
  int cycles = 0;
  int sz = y - x + 1;
  cycles += cnt[1][1];
  cycles += cnt[2][2];
  cycles += cnt[3][3];
  sz -= cycles;
  cycles += min(cnt[1][2], cnt[2][1]);
  sz -= min(cnt[1][2], cnt[2][1]);
  cycles += min(cnt[1][3], cnt[3][1]);
  sz -= min(cnt[1][3], cnt[3][1]);
  cycles += min(cnt[2][3], cnt[3][2]);
  sz -= min(cnt[2][3], cnt[3][2]);
  cycles += sz / 3;
  return cnt[1][3];
}

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