Submission #593491

#	Time	Username	Problem	Language	Result	Execution time	Memory
593491		Pety	Mutating DNA (IOI21_dna)	C++17	100 / 100	148 ms	35936 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];

struct nod {
  int fr[4];
  int cnt[4][4];
  nod () {
    memset(fr, 0, sizeof(fr));
    memset(cnt, 0, sizeof(cnt));
  }
} aint[400002];

nod merge (nod st, nod dr) {
  nod ans;
  for (int i = 1; i <= 3; i++)
    ans.fr[i] = st.fr[i] + dr.fr[i];
  for (int i = 1; i <= 3; i++)
    for (int j = 1; j <= 3; j++)
      ans.cnt[i][j] += st.cnt[i][j] + dr.cnt[i][j];
  return ans;
}

void build (int nod, int st, int dr) {
  if (st == dr) {
    aint[nod].fr[p1[st]]++;
    aint[nod].fr[p2[st]]--;
    aint[nod].cnt[p1[st]][p2[st]]++;
    return;
  }
  int mij = (st + dr) / 2;
  build(2 * nod, st, mij);
  build(2 * nod + 1, mij + 1, dr);
  aint[nod] = merge(aint[2 * nod], aint[2 * nod + 1]);
}

nod query(int nod, int st, int dr, int a, int b) {
  if (a <= st && dr <= b) {
    return aint[nod];
  }
  int mij = (st + dr) / 2;
  if (b <= mij)
    return query(2 * nod, st, mij, a, b);
  else if (a > mij)
    return query(2 * nod + 1, mij + 1, dr, a, b);
  else 
    return merge(query(2 * nod, st, mij, a, b), query(2 * nod + 1, mij + 1, dr, a, b));
}


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]];
  }
  build(1, 1, n);
}

int get_distance (int x, int y) {
  x++;y++;
  
  nod ans = query(1, 1, n, x, y); 
  if (ans.fr[1] != 0 || ans.fr[2] != 0 || ans.fr[3] != 0)
    return -1;
  int cycles = 0;
  int sz = y - x + 1;
  cycles += ans.cnt[1][1];
  cycles += ans.cnt[2][2];
  cycles += ans.cnt[3][3];
  sz -= cycles;
  cycles += min(ans.cnt[1][2], ans.cnt[2][1]);
  sz -= 2 * min(ans.cnt[1][2], ans.cnt[2][1]);
  cycles += min(ans.cnt[1][3], ans.cnt[3][1]);
  sz -= 2 * min(ans.cnt[1][3], ans.cnt[3][1]);
  cycles += min(ans.cnt[2][3], ans.cnt[3][2]);
  sz -= 2 * min(ans.cnt[2][3], ans.cnt[3][2]);
  cycles += sz / 3;
  return y - x + 1 - cycles;
}

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