Submission #589161

#	Time	Username	Problem	Language	Result	Execution time	Memory
589161		l_reho	Mutating DNA (IOI21_dna)	C++17	43 / 100	1587 ms	7280 KiB

dna

#include "dna.h"

#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> MN;
vector<int> MX;

vector<int> V;
string A, B;
vector<bool> visited;

bool subtask1 = true;

void build(int p, int L, int R){
	
	if(L == R){
		MN[p] = L;
		MX[p] = L;
				
		return;
	}
	
	int mid = (L+R)/2;
	
	build(p*2, L, mid);
	build(p*2+1, mid+1, R);
		
	int idx1 = MN[p*2];
	int idx2 = MN[p*2+1];
	
	if(V[idx1] <= V[idx2]) MN[p] = idx1;
	else MN[p] = idx2;
	
	idx1 = MX[p*2];
	idx2 = MX[p*2+1];
	
	if(V[idx1] >= V[idx2]) MX[p] = idx1;
	else MX[p] = idx2;
	
	
	
}

int get(int p, int L, int R, int i, int j, int v){
	
	if(i > R || j < L) return -1;
	
	if(i <= L && R <= j){
		if((v == -1 && V[MN[p]] != -1) || (v == 1 && V[MX[p]] != 1)) return -1;
		int low = L;
		int high = R;
		// int ret = -1;
		
		while(low < high){
			int mid = low +(high-low)/2;
			
			if((v == -1 && V[MN[p*2]] == -1) || (v == 1 && V[MX[p*2]] == 1) ){
				// ret = mid;
				high = mid;
				p*=2;
			}else low = mid+1, p = 2*p+1;
		}
		
		return low;
		
	}
	
	int mid = (L+R)/2;
	
	int ret1 = get(p*2, L, mid, i, j, v);
	if(ret1 != -1) return ret1;
	
	return get(p*2+1, mid+1, R, i, j, v);
	
	
}

void update(int p, int L, int R, int i, int v){
	
	if(i > R || i < L) return;
	
	if(i == R && L == i){
		MX[p] = L;
		MN[p] = L;
		
		V[i] = v;
		return;
	}
	
	int mid = (L+R)/2;
	
	update(p*2, L, mid, i, v);
	update(p*2+1, mid+1, R, i, v);
	
			
	int idx1 = MN[p*2];
	int idx2 = MN[p*2+1];
	
	if(V[idx1] <= V[idx2]) MN[p] = idx1;
	else MN[p] = idx2;
	
	idx1 = MX[p*2];
	idx2 = MX[p*2+1];
	
	if(V[idx1] >= V[idx2]) MX[p] = idx1;
	else MX[p] = idx2;
	
}

void init(std::string a, std::string b) {
	N = a.length();
	
	V.assign(N, 0);
	
	visited.assign(N, false);
	
	MN.assign(N*4+1, 0);
	MX.assign(N*4+1, 0);
	
	A = a;
	B = b;
	
	for(int i = 0; i < N; i++){
		if(a[i] == 'T' && b[i] == 'A') V[i] = 1;
		if(a[i] == 'A' && b[i] == 'T') V[i] = -1;
		if(a[i] == b[i]) V[i] = 0;
	}
	// ATTATATA TATTATTA
	
	build(1, 0, N-1);
	
}

int get_distance(int x, int y) {
	
	if(y-x <= 2){
		
			
		// questo codice va bene se ci sono solo due valori presenti tra i due
		int cntA = 0, cntA1 = 0;
		int cntT = 0, cntT1 = 0;
		int cntC = 0, cntC1 = 0;
		
		for(int i = x; i <= y; i++){
			cntA += A[i] == 'A';
			cntT += A[i] == 'T';
			cntC += A[i] == 'C';
			
			cntA1 += B[i] == 'A';
			cntT1 += B[i] == 'T';
			cntC1 += B[i] == 'C';
			
		}
		
		if(cntA != cntA1 || cntT != cntT1 || cntC != cntC1) return -1;
		
		if(cntA == 1 && cntT == 1 && cntC == 1){
			int cnt = 0;

			for(int i = x; i <= y; i++){
				if(A[i] == B[i]) cnt++;
			}
				
			if(cnt == 3) return 0;
			if(cnt == 1) return 1;
			return 2;
		}
		
		
		map<int, bool> mp;
		int cnt = 0;
		for(int i = x; i <= y; i++){
			
			if((A[i] == B[i]) || mp[i]) continue;
			
			if(i == y)
				return -1;
			
			bool ok = false;
			for(int j = i+1; j <= y; j++){
				if(A[i] == B[j] && B[i] == A[j] && !mp[j]){
					cnt++;
					ok = mp[j] = true;	
					break;
				}
			}
			if(!ok) return -1;
		}
		
		return cnt;
	}
	
	int cnt = 0;
	bool ok = true;
	
	vector<int> save;
	
	for(int i = x; i <= y; i++){
		save.push_back(V[i]);
	}
	
	for(int i = x; i <= y; i++){
		int idx = -1;
		
		if(i == y && V[i] != 0){
			ok = false;
			break;
		}
		if(V[i] == 1)
			idx = get(1, 0, N-1, i+1, y, -1);			
		else if(V[i] == -1)
			idx = get(1, 0, N-1, i+1, y, 1);
		else continue;
		
		
		if(idx == -1) {
			ok = false;
			break;
		}
		
		cnt++;
		
		update(1, 0, N-1, idx, 0);
		
	}
	
	for(int i = x; i <= y; i++){
		update(1, 0, N-1, i, save[i-x]);
	}
	if(!ok) return -1;
	
	return cnt;
}

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