제출 #1234823

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234823		hq77	DNA 돌연변이 (IOI21_dna)	C++20	35 / 100	89 ms	17600 KiB

dna

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

inline array<int,3> combine(const array<int,3>& a, const array<int,3>& b){
	return {a[0] + b[0], a[1] + b[1], a[2] + b[2]};
}
struct node{
    int s,e,m;
    node *l, *r;
    array<int,3> v;
    node(int ss,int ee):s(ss),e(ee),m((s+e)>>1),v{0,0,0}{
        if(s!=e){
            l=new node(s,m);
            r=new node(m+1,e);
        }
    }
    void build(int x,int y,int pos){
        if(s==e){
            v[0]=y;
			v[1]=pos;
			// v[2]=A; v[3]=C; v[4]=T;
            return;
        }
        if(x<=m) l->build(x,y,pos);
        else r->build(x,y,pos);
        v=combine(l->v,r->v);
	}
	array<int,3> query(int x, int y){
        if(x<=s && y>=e)return v;
        if(y<=m) return l->query(x,y);
		if(x > m) return r->query(x, y);
        return combine(l->query(x,m),r->query(m+1,y));
	}

};
vector<vector<int>>v;
// node *st=new node(0,1e5);
node *st=nullptr;
void init(std::string a, std::string b) {
	int n=a.size();
	v.resize(6,vector<int>(n+1,0));
	for(int i=1;i<=n;i++){
		// if(i>1){
			v[0][i]=v[0][i-1];v[1][i]=v[1][i-1];
			v[2][i]=v[2][i-1];v[3][i]=v[3][i-1];
			v[4][i]=v[4][i-1];v[5][i]=v[5][i-1];
		// }
		if(a[i-1]=='A')v[0][i]++; if(b[i-1]=='A')v[3][i]++; 
		if(a[i-1]=='C')v[1][i]++; if(b[i-1]=='C')v[4][i]++; 
		if(a[i-1]=='T')v[2][i]++; if(b[i-1]=='T')v[5][i]++; 
	}
	if(st!=nullptr){
		delete st;
	}
	st=new node(0,n-1);
	for(int i=0;i<a.size();i++){
		if((a[i]=='A' && b[i]=='T') || (a[i]=='T' && b[i]=='C'))st->build(i, 1, 1);
		else if((a[i]=='T' && b[i]=='A') || (a[i]=='C' && b[i]=='T'))st->build(i, -1, 0);
		else if(a[i]=='A' && b[i]=='C')st->build(i, 2, 1);
		else if(a[i]=='C' && b[i]=='A')st->build(i,-2,0);
	}
	
	// for(int i=0;i<a.size();i++){
	// 	if(v[i]==1)st->build(i,v[i],1,0);
	// 	else st->build(i,v[i],0,1);
	// }
}

int get_distance(int x, int y) {
	array<int, 3> result = st->query(x, y);
	// for(int i:result)cout<<i<<" ";
	// cout<<v[0][y+1]-v[0][x]<<" "<<v[3][y+1]-v[3][x]<<" "<<v[1][y+1]-v[1][x]<<" "<<v[4][y+1]-v[4][x]<<" "<<v[2][y+1]-v[2][x]<<" "<<v[5][y+1]-v[5][x]<<" ";
	if(v[0][y+1]-v[0][x] != v[3][y+1]-v[3][x]) return -1;
	if(v[1][y+1]-v[1][x] != v[4][y+1]-v[4][x]) return -1;
	if(v[2][y+1]-v[2][x] != v[5][y+1]-v[5][x]) return -1;
	if(result[0]!=0)return -1;
	else return result[1];
}

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