Submission #626309

#	Time	Username	Problem	Language	Result	Execution time	Memory
626309		juancarlovieri	Mutating DNA (IOI21_dna)	C++17	84 / 100	1527 ms	7636 KiB

dna

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

int pre[100005][3][3];
int n;
string a, b;

void init(std::string A, std::string B) {
  a = A, b = B;
  n = a.length();
  for (int i = 0; i < n; ++i) {
    if (a[i] == 'A') a[i] = 'a';
    else if (a[i] == 'C') a[i] = 'b';
    else a[i] = 'c';
    if (b[i] == 'A') b[i] = 'a';
    else if (b[i] == 'C') b[i] = 'b';
    else b[i] = 'c';
  }
  for (int i = 0; i < n; ++i) {
    pre[i][a[i] - 'a'][b[i] - 'a']++;
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) pre[i][j][k] += pre[i - 1][j][k];
    }
  }
  // for (int i = 0; i < 3; ++i) {
  //   for (int j = 0; j < 3; ++j) cout << pre[n - 1][i][j] << ' ';
  //   cout << endl;
  // }
}

int arr[3][3];

int get_distance(int x, int y) {
  // cout << y << endl;
  memset(arr, 0, sizeof arr);
  for (int i = 0; i < 3; ++i) {
    for (int j = 0; j < 3; ++j) {
      arr[i][j] = pre[y][i][j];
      if (x) arr[i][j] -= pre[x - 1][i][j];
      // cout << pre[n - 1][i][j] << ' ';
      // cout << arr[i][j] << ' ';
    }
    // cout << endl;
    // cout << endl;
  }
  int ans = 0;
  for (int rep = 0; rep < 100; ++rep) {
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        if (i == j) continue;
        if (arr[i][j] == 0) continue;
        int take = arr[i][j];
        take = min(take, arr[j][i]);
        arr[i][j] -= take;
        arr[j][i] -= take;
        ans += take;
      }
    }
  }
  for (int rep = 0; rep < 100; ++rep) {
    for (int i = 0; i < 3; ++i) {
      for (int j = 0; j < 3; ++j) {
        if (i == j) continue;
        if (arr[i][j] == 0) continue;
        int take = arr[i][j];
        take = min(take, arr[j][i]);
        arr[i][j] -= take;
        arr[j][i] -= take;
        ans += take;
        if (arr[i][j] == 0) continue;
        for (int k = 0; k < 3; ++k) {
          if (arr[j][k] == 0) continue;
          if (j == k) continue;
          int take = arr[i][j];
          take = min(take, arr[j][k]);
          arr[i][j] -= take;
          arr[j][k] -= take;
          arr[i][k] += take;
          ans += take;
        }
      }
    }
  }
  int can = 1;
  for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) if (i != j && arr[i][j] != 0) can = 0;
  if (!can) {
    // int cnt = 0;
    vector<vector<int>> cnt(2, vector<int> (3, 0));
    for (int i = x; i <= y; ++i) {
      ++cnt[0][a[i] - 'a'];
      ++cnt[1][b[i] - 'a'];
    }
    int cann = 1;
    for (int i = 0; i < 3; ++i) if (cnt[0][i] != cnt[1][i]) cann = 0;
    assert(cann == 0);
    // cout << cnt[0][0] << ' ' << cnt[1][0] << endl;
  }
  if (!can) return -1;
  return ans;
}

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