oj.uz

Submission #970734

# Submission time Handle Problem Language Result Execution time Memory
970734 2024-04-27T07:40:08 Z elotelo966 Mutating DNA (IOI21_dna) C++17
21 / 100
 29 ms 8028 KB 
#include <bits/stdc++.h>
#include "dna.h"

using namespace std;

#define lim 100005

int n;

int pre_a_a[lim],pre_b_a[lim];// a string a char   -----  b string a char
int pre_a_t[lim],pre_b_t[lim];// a string t char   -----  b string t char
int pre_a_c[lim],pre_b_c[lim];// a string c char   -----  b string c char

int at[lim],ta[lim],ac[lim],ca[lim],tc[lim],ct[lim];

int sum[lim];

inline bool querya(int x,int y){
	if(pre_a_a[y+1]-pre_a_a[x]==pre_b_a[y+1]-pre_b_a[x])return 1;
	return 0;
}

inline bool queryt(int x,int y){
	if(pre_a_t[y+1]-pre_a_t[x]==pre_b_t[y+1]-pre_b_t[x])return 1;
	return 0;
}

inline bool queryc(int x,int y){
	if(pre_a_c[y+1]-pre_a_c[x]==pre_b_c[y+1]-pre_b_c[x])return 1;
	return 0;
}

void init(string a,string b) {
	n=a.length();
	for(int i=0;i<n;i++){
		pre_a_a[i+1]=pre_a_a[i];
		if(a[i]=='A')pre_a_a[i+1]++;
		
		pre_b_a[i+1]=pre_b_a[i];
		if(b[i]=='A')pre_b_a[i+1]++;
		
		pre_a_t[i+1]=pre_a_t[i];
		if(a[i]=='T')pre_a_t[i+1]++;
		
		pre_b_t[i+1]=pre_b_t[i];
		if(b[i]=='T')pre_b_t[i+1]++;
		
		pre_a_c[i+1]=pre_a_c[i];
		if(a[i]=='C')pre_a_c[i+1]++;
		
		pre_b_c[i+1]=pre_b_c[i];
		if(b[i]=='C')pre_b_c[i+1]++;
		
		sum[i+1]=sum[i];
		if(a[i]!=b[i])sum[i+1]++;
		
		ac[i+1]=ac[i],at[i+1]=at[i];
		ca[i+1]=ca[i],ct[i+1]=ct[i];
		ta[i+1]=ta[i],tc[i+1]=tc[i];
		
		if(a[i]=='A'){
			if(b[i]=='C')ac[i+1]++;
			else if(b[i]=='T')at[i+1]++;
		}
		else if(a[i]=='C'){
			if(b[i]=='A')ca[i+1]++;
			else if(b[i]=='T')ct[i+1]++;
		}
		else{
			if(b[i]=='A')ta[i+1]++;
			else if(b[i]=='C')tc[i+1]++;
		}
	}
}

int get_distance(int x, int y) {
	if(querya(x,y) && queryt(x,y) && queryc(x,y)){
		int cev=0;
		int anormal=sum[y+1]-sum[x];
		cev+=min(at[y+1]-at[x],ta[y+1]-ta[x]);
		cev+=min(ac[y+1]-ac[x],ca[y+1]-ca[x]);
		cev+=min(tc[y+1]-tc[x],ct[y+1]-ct[x]);
		anormal-=cev;
		cev+=(anormal/3)*2;
		return cev;
	}
	else return -1;
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7440 KB Output is correct
2 Correct 28 ms 8028 KB Output is correct
3 Correct 29 ms 7456 KB Output is correct
4 Correct 28 ms 7868 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 448 KB Output is correct
7 Correct 1 ms 536 KB Output is correct

Subtask #2
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 5940 KB Output is correct
5 Correct 5 ms 5980 KB Output is correct
6 Correct 5 ms 6232 KB Output is correct
7 Incorrect 4 ms 5724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 5940 KB Output is correct
5 Correct 5 ms 5980 KB Output is correct
6 Correct 5 ms 6232 KB Output is correct
7 Incorrect 4 ms 5724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 5 ms 5940 KB Output is correct
5 Correct 5 ms 5980 KB Output is correct
6 Correct 5 ms 6232 KB Output is correct
7 Incorrect 4 ms 5724 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 7440 KB Output is correct
2 Correct 28 ms 8028 KB Output is correct
3 Correct 29 ms 7456 KB Output is correct
4 Correct 28 ms 7868 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 448 KB Output is correct
7 Correct 1 ms 536 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 5 ms 5940 KB Output is correct
12 Correct 5 ms 5980 KB Output is correct
13 Correct 5 ms 6232 KB Output is correct
14 Incorrect 4 ms 5724 KB Output isn't correct
15 Halted 0 ms 0 KB -