oj.uz

답안 #442060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442060 2021-07-07T00:56:04 Z jlozano254 DNA 돌연변이 (IOI21_dna) C++17
100 / 100
 411 ms 101188 KB 
#include "dna.h"
#include <map>
#include <vector>

const int MAXN = 1e5 + 5;

std::vector<std::map<char, int>> aDP(MAXN);
std::vector<std::map<char, int>> bDP(MAXN);
std::vector<std::map<char, std::map<char, int>>> abDP(MAXN);

void init(std::string a, std::string b) {
  for (int i = 0; i < (int) a.length(); ++i)
  {
    aDP[i + 1] = aDP[i];
    bDP[i + 1] = bDP[i];
    abDP[i + 1] = abDP[i];

    if (a[i] != b[i])
    {
      aDP[i + 1][a[i]]++;
      bDP[i + 1][b[i]]++;
      abDP[i + 1][a[i]][b[i]]++;
    }
  }
}

int get_distance(int x, int y) {
  y++;

  int aAcumA = aDP[y]['A'] - aDP[x]['A'];
  int aAcumC = aDP[y]['C'] - aDP[x]['C'];
  int aAcumT = aDP[y]['T'] - aDP[x]['T'];

  int bAcumA = bDP[y]['A'] - bDP[x]['A'];
  int bAcumC = bDP[y]['C'] - bDP[x]['C'];
  int bAcumT = bDP[y]['T'] - bDP[x]['T'];

  if (aAcumA != bAcumA || aAcumC != bAcumC || aAcumT != bAcumT) return -1;

  std::map<char, std::map<char, int>> comb;

  comb['A']['C'] = abDP[y]['A']['C'] - abDP[x]['A']['C'];
  comb['C']['A'] = abDP[y]['C']['A'] - abDP[x]['C']['A'];

  comb['A']['T'] = abDP[y]['A']['T'] - abDP[x]['A']['T'];
  comb['T']['A'] = abDP[y]['T']['A'] - abDP[x]['T']['A'];

  comb['C']['T'] = abDP[y]['C']['T'] - abDP[x]['C']['T'];
  comb['T']['C'] = abDP[y]['T']['C'] - abDP[x]['T']['C'];

  int distance = 0;

  distance += std::min(comb['A']['C'], comb['C']['A']);
  distance += std::min(comb['A']['T'], comb['T']['A']);
  distance += std::min(comb['C']['T'], comb['T']['C']);

  distance += std::abs(comb['A']['T'] - comb['T']['A']) << 1;

  return distance;
}

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 90308 KB Output is correct
2 Correct 383 ms 91068 KB Output is correct
3 Correct 329 ms 93328 KB Output is correct
4 Correct 333 ms 100856 KB Output is correct
5 Correct 9 ms 14284 KB Output is correct
6 Correct 9 ms 14284 KB Output is correct
7 Correct 9 ms 14328 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 9 ms 14284 KB Output is correct
3 Correct 9 ms 14284 KB Output is correct
4 Correct 98 ms 61432 KB Output is correct
5 Correct 86 ms 62068 KB Output is correct
6 Correct 86 ms 61712 KB Output is correct
7 Correct 79 ms 58736 KB Output is correct
8 Correct 88 ms 62020 KB Output is correct
9 Correct 94 ms 62060 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 9 ms 14284 KB Output is correct
3 Correct 9 ms 14284 KB Output is correct
4 Correct 98 ms 61432 KB Output is correct
5 Correct 86 ms 62068 KB Output is correct
6 Correct 86 ms 61712 KB Output is correct
7 Correct 79 ms 58736 KB Output is correct
8 Correct 88 ms 62020 KB Output is correct
9 Correct 94 ms 62060 KB Output is correct
10 Correct 393 ms 90152 KB Output is correct
11 Correct 375 ms 91076 KB Output is correct
12 Correct 387 ms 88724 KB Output is correct
13 Correct 396 ms 90408 KB Output is correct
14 Correct 411 ms 93372 KB Output is correct
15 Correct 407 ms 94148 KB Output is correct
16 Correct 345 ms 80784 KB Output is correct
17 Correct 361 ms 82468 KB Output is correct
18 Correct 362 ms 85308 KB Output is correct
19 Correct 201 ms 62480 KB Output is correct
20 Correct 201 ms 63696 KB Output is correct
21 Correct 218 ms 65860 KB Output is correct

Subtask #4
28.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 14284 KB Output is correct
2 Correct 9 ms 14284 KB Output is correct
3 Correct 9 ms 14284 KB Output is correct
4 Correct 98 ms 61432 KB Output is correct
5 Correct 86 ms 62068 KB Output is correct
6 Correct 86 ms 61712 KB Output is correct
7 Correct 79 ms 58736 KB Output is correct
8 Correct 88 ms 62020 KB Output is correct
9 Correct 94 ms 62060 KB Output is correct
10 Correct 140 ms 92220 KB Output is correct
11 Correct 141 ms 99396 KB Output is correct
12 Correct 140 ms 93832 KB Output is correct
13 Correct 165 ms 99028 KB Output is correct
14 Correct 155 ms 99488 KB Output is correct
15 Correct 140 ms 99400 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 402 ms 90308 KB Output is correct
2 Correct 383 ms 91068 KB Output is correct
3 Correct 329 ms 93328 KB Output is correct
4 Correct 333 ms 100856 KB Output is correct
5 Correct 9 ms 14284 KB Output is correct
6 Correct 9 ms 14284 KB Output is correct
7 Correct 9 ms 14328 KB Output is correct
8 Correct 9 ms 14284 KB Output is correct
9 Correct 9 ms 14284 KB Output is correct
10 Correct 9 ms 14284 KB Output is correct
11 Correct 98 ms 61432 KB Output is correct
12 Correct 86 ms 62068 KB Output is correct
13 Correct 86 ms 61712 KB Output is correct
14 Correct 79 ms 58736 KB Output is correct
15 Correct 88 ms 62020 KB Output is correct
16 Correct 94 ms 62060 KB Output is correct
17 Correct 393 ms 90152 KB Output is correct
18 Correct 375 ms 91076 KB Output is correct
19 Correct 387 ms 88724 KB Output is correct
20 Correct 396 ms 90408 KB Output is correct
21 Correct 411 ms 93372 KB Output is correct
22 Correct 407 ms 94148 KB Output is correct
23 Correct 345 ms 80784 KB Output is correct
24 Correct 361 ms 82468 KB Output is correct
25 Correct 362 ms 85308 KB Output is correct
26 Correct 201 ms 62480 KB Output is correct
27 Correct 201 ms 63696 KB Output is correct
28 Correct 218 ms 65860 KB Output is correct
29 Correct 140 ms 92220 KB Output is correct
30 Correct 141 ms 99396 KB Output is correct
31 Correct 140 ms 93832 KB Output is correct
32 Correct 165 ms 99028 KB Output is correct
33 Correct 155 ms 99488 KB Output is correct
34 Correct 140 ms 99400 KB Output is correct
35 Correct 9 ms 14284 KB Output is correct
36 Correct 317 ms 93312 KB Output is correct
37 Correct 322 ms 100784 KB Output is correct
38 Correct 310 ms 96008 KB Output is correct
39 Correct 315 ms 101188 KB Output is correct
40 Correct 317 ms 101180 KB Output is correct
41 Correct 142 ms 99468 KB Output is correct
42 Correct 291 ms 95980 KB Output is correct
43 Correct 301 ms 101176 KB Output is correct
44 Correct 299 ms 101176 KB Output is correct
45 Correct 240 ms 83528 KB Output is correct
46 Correct 301 ms 87788 KB Output is correct
47 Correct 263 ms 88012 KB Output is correct