글 읽기 - 종만북 코드 질문

p_ce1052 4년 전 0

삽입정렬 뒤집기 라는 문제입니다. 714p 부터 시작하는 treap을 구현해서 푸는데 종만북의 코드를 옮겨쓰고 메인 함수만 직접 작성해서 문제를 풀었는데 테스트 케이스를 넣는 과정에서 답을 출력하지 못하고 중간에 런타임 에러가 발생합니다. 주석처리하면서 런타임 에러 발생 지점을 보니 erase문이 들어갔을 때부터 런타임 에러가 발생하는데 어디서 문제인지 잘 모르겠습니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef int KeyType;

struct Node{
	KeyType key;
	int size,priority;
	Node*left,*right;
	Node(KeyType data){
		key=data;
		priority=rand();
		size=1;
		left=NULL;
		right=NULL;
	}
	void setleft(Node*nleft){
		left=nleft;
		calc();
	}
	void setright(Node*nright){
		right=nright;
		calc();
	}
	void calc(){
		size=1;
		if(left) size+=left->size;
		if(right) size+=right->size;
	}
};
typedef pair<Node*,Node*> nodepair;
nodepair split(Node*root,KeyType key){
	if(root==NULL) return nodepair(NULL,NULL);
	if(root->key<key){
		nodepair rs = split(root->right,key);
		root->setright(rs.first);
		return nodepair(root,rs.second);
	}
	nodepair ls = split(root->left,key);
	root->setleft(ls.second);
	return nodepair(ls.first,root);
}
Node*insert(Node*root,Node*node){
	if(root==NULL) return node;
	if(root->priority < node->priority){
		nodepair splitted = split(root,node->key);
		node->setleft(splitted.first);
		node->setright(splitted.second);
		return node;
	}
	if(root->key < node->key) root->setright(insert(root->right,node));
	else root->setleft(insert(root->left,node));
	return root;
}
Node*merge(Node*a,Node*b){
	if(a==NULL) return b;
	if(b==NULL) return a;
	if(a->priority < b->priority){
		b->setleft(merge(a,b->left));
		return b;
	}
	a->setright(merge(a->right,b));
	return a;
}
Node*erase(Node*root, KeyType key){
	if(root == NULL) return NULL;
	if(root->key < key){
		root->setright(erase(root->right,key));
	}
	else if(root->key >key){
		root->setleft(erase(root->left,key));
	}
	else{
		Node*temp = merge(root->left,root->right);
		delete root;
		return temp;
	}
	return root;
}
Node* kth(Node*root, int k){
	int lsize=0;
	if(root->left) root->left->size;
	if(k<=lsize) return kth(root->left,k);
	else if(k==lsize+1){
		return root;
	}
	else{
		return kth(root->right,k-lsize-1);
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	int t;
	cin>>t;
	while(t--){
		int n;
		Node*root=NULL;
		cin>>n;
		vector<int>reversed_selection(n);
		for(int i=0; i<n; i++){
			cin>>reversed_selection[i];
		}
		for(int i=1; i<=n; i++){
			root=insert(root,new Node(i));
		}
		for(int i=n-1; i>=0; i--){
			int larger = reversed_selection[i];
			Node*k = kth(root,i+1-larger);
			reversed_selection[i]=k->key;
			root=erase(root,k->key);
		}
		for(int i=0; i<n; i++) cout<<reversed_selection[i]<<" ";
		cout<<'\n';	
	}
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

종만북 코드 질문

p_ce1052 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말