oj.uz

답안 #938727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938727 2024-03-05T13:29:26 Z Hugo1729 DNA 돌연변이 (IOI21_dna) C++17
0 / 100
 29 ms 8532 KB 
#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
	
string a,b;
int n;
int pref[100001][3][3]={0},pa[100001][3]={0},pb[100001][3]={0};
map<char,int> m;
	
void init(string c, string d) {
	a=c;b=d;
	n=a.size();
	m['A']=0;
	m['C']=1;
	m['T']=2;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			pa[i+1][j]=pa[i][j];
			pb[i+1][j]=pb[i][j];
			for(int k=0;k<3;k++){
				pref[i+1][j][k]=pref[i+1][j][k];
			}
		}
		pa[i+1][m[a[i]]]++;
		pb[i+1][m[b[i]]]++;
		pref[i+1][m[a[i]]][m[b[i]]]++;
	}
	
}
	
int get_distance(int x, int y) {
	int dista1=pa[y+1][0]-pa[x][0];
	int distb1=pb[y+1][0]-pb[x][0];
	int dista2=pa[y+1][1]-pa[x][1];
	int distb2=pb[y+1][1]-pb[x][1];
	
	if(dista1==distb1&&dista2==distb2){
		int ans=0,l=y-x+1;
		for(int i=0;i<3;i++){
			for(int j=0;j<=i;j++){
				int sus1=pref[y+1][i][j]-pref[x][i][j];
				int sus2=pref[y+1][j][i]-pref[x][j][i];
				if(i==j)l-=sus1;
				else{
					int sussy=min(sus1,sus2);
					l-=2*sussy;
					ans+=sussy;
				}
			}
		}
		int among=l/3;
		ans+=among*2;
		return ans;

	} else return -1;
}

Subtask #1
0.0 / 21.0

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

Subtask #2
0.0 / 22.0

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

Subtask #3
0.0 / 13.0

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

Subtask #4
0.0 / 28.0

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

Subtask #5
0.0 / 16.0

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