Submission #476256

#	Time	Username	Problem	Language	Result	Execution time	Memory
476256		Mahmudul_Kabir	Mutating DNA (IOI21_dna)	C++17	0 / 100	1111 ms	2097156 KiB

dna

#include "dna.h"

#include "bits/stdc++.h"

#define sp <<" "
#define el <<"\n"
#define S second
#define F first
#define pb push_back
#define all(ar) ar.begin(),ar.end() 
#define pii pair<int,int> 

 
using namespace std;
using ll = long long; 
using ld = long double;
 
const int mod = 100000007;
const int si = 100005;
const int inf = 7000; 

ll po[si][3], pt[si][3],n; 
unordered_map<char,ll> hau = {{'A',0},{'T',1},{'C',2}}; 
ll str[si * 4]; 

void make(int x,int y,int node,string &a,string &b){
	if(x == y){
		str[node] = a[x] == b[x]; 
		return; 
	}
	int mid = x + (y - x)/2, lef = node * 2; 
	make(x,mid,lef,a,b); make(mid+1,y,lef + 1,a,b); 
	str[node] = str[lef] + str[lef+1]; 
	return; 
}

int que(int a,int b,int l,int r,int node){
	if(b < l || r < a) return 0; 
	if(a >= l && r <= b) return str[node]; 
	int mid = a + (b - a)/2, lef = node * 2; 
	return que(a,mid,l,r,lef) + que(mid+1,b,l,r,lef+1);  
}


void init(std::string a, std::string b){
	n = a.size(); 
	memset(po,0,sizeof(po)); memset(pt,0,sizeof(pt)); 
	po[0][hau[a[0]]] += 1; pt[0][hau[b[0]]] += 1; 
	for(int i = 1; i < n; i++){
		for(int j = 0; j < 3; j++){
			po[i][j] = po[i - 1][j]; 
			pt[i][j] = pt[i - 1][j];
		}
		po[i][hau[a[i]]] += 1;
		pt[i][hau[b[i]]] += 1; 
	}
	memset(str,0,sizeof(str)); 
	make(0,n-1,1,a,b); 
	return; 
}

int get(int x,int y,int i,bool t){
	ll ans = t ? pt[y][i] : po[y][i]; 
	if(x) ans -= t ? pt[x - 1][i] : po[x - 1][i]; 
	return ans;  
}

bool hobe(int x,int y){
	return (get(x,y,0,0) == get(x,y,0,1)) && (get(x,y,1,0) == get(x,y,1,1)) && (get(x,y,2,0) == get(x,y,2,1)); 
}

int get_distance(int x, int y) {
	if(!hobe) return -1; 
	return que(0,n - 1,x,y,1)/2;
}

Compilation message (stderr)

dna.cpp: In function 'int get_distance(int, int)':
dna.cpp:73:6: warning: the address of 'bool hobe(int, int)' will never be NULL [-Waddress]
   73 |  if(!hobe) return -1;
      |      ^~~~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 22
• Subtask 3: 0 / 13
• Subtask 4: 0 / 28
• Subtask 5: 0 / 16