제출 #589061

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589061		l_reho	DNA 돌연변이 (IOI21_dna)	C++17	22 / 100	1578 ms	5780 KiB

dna

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

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

vector<int> V;
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);
	
	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){
		map<int, bool> mp;
		int cnt = 0;
		for(int i = x; i <= y; i++){
			
			if(V[i] == 0 || mp[i]) continue;
			
			if(i == y) {
				if(!mp[i] && V[i] != 0) return -1;
				return cnt;
			}
			
			bool ok = false;
			for(int j = i+1; j <= y; j++){
				if(V[j] == -V[i] && !mp[j]){
					cnt++;
					ok = mp[j] = true;	
					break;
				}
			}
			if(!ok) return -1;
		}
		
		return cnt;
	}
	
	vector<int> init = V;
	
	int cnt = 0;
	bool ok = true;
	
	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, init[i]);
	}
	if(!ok) return -1;
	
	return cnt;
}

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