oj.uz

답안 #527672

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
527672 2022-02-18T01:41:34 Z vivaan_gupta DNA 돌연변이 (IOI21_dna) C++17
56 / 100
 38 ms 10052 KB 
#include "dna.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
map<char,int> mp;

string A, B;
int cnt[N][3];
int cnt2[N][3];
int bad[N];
int all[N][3][3], all2[N][3][3];



void init(std::string a, std::string b) {
	A = a, B = b;
	mp['A'] = 0;
	mp['C'] = 1;
	mp['T'] = 2;
	for(int i = 0;i < a.size();i++){
		int tmp = mp[a[i]];
		int gg = (a[i] != b[i]);
		cnt[i][tmp] ++;
		bad[i] = gg;
		if(i > 0){
			bad[i] += bad[i-1];
			for(int j = 0;j < 3;j++){
				cnt[i][j] += cnt[i-1][j];
			}
		}	

		int tmp2 = mp[b[i]];
		cnt2[i][tmp2] ++;
		if(i > 0){
			for(int j = 0;j < 3;j++){
				cnt2[i][j] += cnt2[i-1][j];
			}
		}	

		all[i][tmp][tmp2] ++;
		if(i > 0){
			for(int j = 0;j< 3;j++){
				for(int k =0;k<3;k++){
					all[i][j][k] += all[i-1][j][k];
				}
			}
		}

	}
	return;
}

int get_distance(int x, int y) {

	bool ok = 1;
	for(int i = 0;i < 3;i++){
		int sum = cnt[y][i];
		if(x > 0) sum -= cnt[x - 1][i];
		
		int sum2 = cnt2[y][i];
		if(x > 0) sum2 -= cnt2[x - 1][i];
		
		ok &= (sum == sum2);
	}
	if(!ok) return -1;

	int sum = bad[y];
	if(x > 0) sum -= bad[x-1];
	int left = sum;
	sum = 0;
	for(int a = 0;a < 3;a++){
		for(int b = a + 1;b < 3;b++){
			// a b
			// b a
			int tmp1 = all[y][a][b];
			int tmp2 = all[y][b][a];
			if(x > 0){
				tmp1 -= all[x - 1][a][b];
				tmp2 -= all[x - 1][b][a];
			}
			left -= min(tmp1, tmp2) * 2;
			sum += min(tmp1, tmp2);
		}
	}

	return sum + max((int)0, left - 1);
}

Compilation message

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

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 8616 KB Output is correct
2 Correct 37 ms 8644 KB Output is correct
3 Correct 36 ms 8016 KB Output is correct
4 Correct 36 ms 10052 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 220 KB Output is correct
4 Correct 6 ms 7200 KB Output is correct
5 Correct 6 ms 7244 KB Output is correct
6 Correct 6 ms 7244 KB Output is correct
7 Correct 6 ms 6860 KB Output is correct
8 Correct 6 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 220 KB Output is correct
4 Correct 6 ms 7200 KB Output is correct
5 Correct 6 ms 7244 KB Output is correct
6 Correct 6 ms 7244 KB Output is correct
7 Correct 6 ms 6860 KB Output is correct
8 Correct 6 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 36 ms 8644 KB Output is correct
11 Correct 37 ms 8676 KB Output is correct
12 Correct 35 ms 8516 KB Output is correct
13 Correct 38 ms 8780 KB Output is correct
14 Correct 37 ms 9028 KB Output is correct
15 Correct 38 ms 8916 KB Output is correct
16 Correct 32 ms 8516 KB Output is correct
17 Correct 33 ms 8752 KB Output is correct
18 Correct 33 ms 9028 KB Output is correct
19 Correct 32 ms 8596 KB Output is correct
20 Correct 31 ms 8776 KB Output is correct
21 Correct 33 ms 9028 KB Output is correct

Subtask #4
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 220 KB Output is correct
4 Correct 6 ms 7200 KB Output is correct
5 Correct 6 ms 7244 KB Output is correct
6 Correct 6 ms 7244 KB Output is correct
7 Correct 6 ms 6860 KB Output is correct
8 Correct 6 ms 7244 KB Output is correct
9 Correct 5 ms 7244 KB Output is correct
10 Correct 6 ms 6704 KB Output is correct
11 Correct 6 ms 7524 KB Output is correct
12 Incorrect 7 ms 6996 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 8616 KB Output is correct
2 Correct 37 ms 8644 KB Output is correct
3 Correct 36 ms 8016 KB Output is correct
4 Correct 36 ms 10052 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 0 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 220 KB Output is correct
11 Correct 6 ms 7200 KB Output is correct
12 Correct 6 ms 7244 KB Output is correct
13 Correct 6 ms 7244 KB Output is correct
14 Correct 6 ms 6860 KB Output is correct
15 Correct 6 ms 7244 KB Output is correct
16 Correct 5 ms 7244 KB Output is correct
17 Correct 36 ms 8644 KB Output is correct
18 Correct 37 ms 8676 KB Output is correct
19 Correct 35 ms 8516 KB Output is correct
20 Correct 38 ms 8780 KB Output is correct
21 Correct 37 ms 9028 KB Output is correct
22 Correct 38 ms 8916 KB Output is correct
23 Correct 32 ms 8516 KB Output is correct
24 Correct 33 ms 8752 KB Output is correct
25 Correct 33 ms 9028 KB Output is correct
26 Correct 32 ms 8596 KB Output is correct
27 Correct 31 ms 8776 KB Output is correct
28 Correct 33 ms 9028 KB Output is correct
29 Correct 6 ms 6704 KB Output is correct
30 Correct 6 ms 7524 KB Output is correct
31 Incorrect 7 ms 6996 KB Output isn't correct
32 Halted 0 ms 0 KB -