oj.uz

Submission #437682

# Submission time Handle Problem Language Result Execution time Memory
437682 2021-06-26T20:27:43 Z Haunted_Cpp Mutating DNA (IOI21_dna) C++17
0 / 100
 47 ms 6872 KB 
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 1e5 + 5;
int N;

vector<int> aA(MAX_N), aC(MAX_N), aT(MAX_N);
vector<int> bA(MAX_N), bC(MAX_N), bT(MAX_N);

vector<int> AC(MAX_N), AT(MAX_N);
vector<int> CA(MAX_N), CT(MAX_N);
vector<int> TA(MAX_N), TC(MAX_N);

void get(const string &w, vector<int> &arr, char c) {
  arr[0] = (w[0] == c);
  for (int i = 1; i < N; i++) {
    arr[i] = arr[i - 1] + (w[i] == c);
  }
}

void init(string a, string b) {
  N = a.size();
  get(a, aA, 'A');
  get(a, aC, 'C');
  get(a, aT, 'T');
  get(b, bA, 'A');
  get(b, bC, 'C');
  get(b, bT, 'T');
  for (int i = 0; i < N; i++) {
    AC[i] += (a[i] == 'A' && b[i] == 'C') + (i >= 0 ? AC[i - 1] : 0);
    AT[i] += (a[i] == 'A' && b[i] == 'T') + (i >= 0 ? AT[i - 1] : 0);
    CA[i] += (a[i] == 'C' && b[i] == 'A') + (i >= 0 ? CA[i - 1] : 0);
    CT[i] += (a[i] == 'C' && b[i] == 'T') + (i >= 0 ? CT[i - 1] : 0);
    TA[i] += (a[i] == 'T' && b[i] == 'A') + (i >= 0 ? TA[i - 1] : 0);
    TC[i] += (a[i] == 'T' && b[i] == 'C') + (i >= 0 ? TC[i - 1] : 0);
  }
}

int rq(const vector<int> &arr, int l, int r) {
  assert(l <= r);
  assert(arr[r] - (l > 0 ? arr[l - 1] : 0) >= 0);
  return arr[r] - (l > 0 ? arr[l - 1] : 0);
}

int get_distance(int x, int y) {
  if (rq(aA, x, y) != rq(bA, x, y)) return -1;
  if (rq(aC, x, y) != rq(bC, x, y)) return -1;
  if (rq(aT, x, y) != rq(bT, x, y)) return -1;
  int res = 0;
  int got = min(rq(CA, x, y), rq(AC, x, y)) + min(rq(TA, x, y), rq(AT, x, y)) + min(rq(TC, x, y), rq(CT, x, y));
  res += got;
  res += max (0, (y - x + 1) - (2 * got) - 1); 
	return res;
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 6872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 7 ms 5580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 7 ms 5580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Incorrect 7 ms 5580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 6872 KB Output isn't correct
2 Halted 0 ms 0 KB -