oj.uz

답안 #437078

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
437078 2021-06-25T18:41:11 Z aryan12 DNA 돌연변이 (IOI21_dna) C++17
0 / 100
 41 ms 8708 KB 
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5; 
int prefA[N][3], prefB[N][3];
int pref[N][3][3];

void init(string a, string b) {
	int n = a.size();
	int arrA[n + 1], arrB[n + 1];
	for(int i = 0; i < a.size(); i++) {
		arrA[i + 1] = ((a[i] == 'A') ? 0 : ((a[i] == 'C') ? 1 : 2));
		arrB[i + 1] = ((b[i] == 'A') ? 0 : ((b[i] == 'C') ? 1 : 2));
	}
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < 3; j++) {
			prefA[i][j] = 0;
			prefB[i][j] = 0;
			for(int k = 0; k < 3; k++) {
				pref[i][j][k] = 0;
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		for(int j = 0; j < 3; j++) {
			prefA[i][j] = prefA[i - 1][j];
			prefB[i][j] = prefB[i - 1][j];
			for(int k = 0; k < 3; k++) {
				pref[i][j][k] = pref[i - 1][j][k];
			}
		}
		prefA[i][arrA[i]]++;
		prefB[i][arrB[i]]++;
		pref[i][arrA[i]][arrB[i]]++;
	}
}

int get_distance(int x, int y) {
	x++, y++;
	if((prefA[y][0] - prefA[x - 1][0] != prefB[y][0] - prefB[x - 1][0]) || (prefA[y][1] - prefA[x - 1][1] != prefB[y][1] - prefB[x - 1][1]) || (prefA[y][2] - prefA[x - 1][2] != prefB[y][2] - prefB[x - 1][2])) {
		return -1;
	}
	int res = 0;
	int ans[3] = {0, 0, 0};
	int carry[3] = {0, 0, 0};
	ans[0] += min(pref[y][0][1] - pref[x - 1][0][1], pref[y][1][0] - pref[x - 1][1][0]);
	ans[1] += min(pref[y][0][2] - pref[x - 1][0][2], pref[y][2][0] - pref[x - 1][2][0]);
	ans[2] += min(pref[y][1][2] - pref[x - 1][1][2], pref[y][2][1] - pref[x - 1][2][1]);
	int sum = ans[0] + ans[1] + ans[2];
	res = sum;
	res += (y - x + 1 - sum) - 1;
	return res;
}

Compilation message

dna.cpp: In function 'void init(std::string, std::string)':
dna.cpp:12:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |  for(int i = 0; i < a.size(); i++) {
      |                 ~~^~~~~~~~~~
dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:46:6: warning: unused variable 'carry' [-Wunused-variable]
   46 |  int carry[3] = {0, 0, 0};
      |      ^~~~~

Subtask #1
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 8708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 4 ms 6092 KB Output is correct
4 Incorrect 9 ms 7500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 4 ms 6092 KB Output is correct
4 Incorrect 9 ms 7500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 6092 KB Output is correct
2 Correct 4 ms 6092 KB Output is correct
3 Correct 4 ms 6092 KB Output is correct
4 Incorrect 9 ms 7500 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 41 ms 8708 KB Output isn't correct
2 Halted 0 ms 0 KB -