学步园

8.5

8.5.1 Problem E 

preorder

#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 100001;

struct tree{
	int l,r;
	int num;
	}Tree[MAXN];

int last,index[MAXN],num[MAXN];

void maketree(int root,int n){
	if (Tree[root].num >= n){
		if (Tree[root].l == 0){
			Tree[++last].num = n;
			Tree[last].l = Tree[last].r = 0;
			Tree[root].l= last;
			}
		else maketree(Tree[root].l,n);
		}else{
			if (Tree[root].r == 0){
				Tree[++last].num = n;
				Tree[last].l = Tree[last].r = 0;
				Tree[root].r = last;
				}
			else maketree(Tree[root].r,n);
		}
	}

void Main_Maketree(int num[],int n){
	int i;
	memset(Tree,0,sizeof(Tree));
	Tree[0].num = num[0];
	last = 0;
	for (i=1;i<n;++i)
		maketree(0,num[i]);
	}

void preorder(int root){
	index[root] = last++;
	if (Tree[root].l)
		preorder(Tree[root].l);
	if (Tree[root].r)
		preorder(Tree[root].r);
	}

int findID(int root,int n){
	if (Tree[root].num >= n){
		if (Tree[root].l)
			findID(Tree[root].l,n);
		else
			return -1;
		}
	else{
		if (Tree[root].r){
			int ret=findID(Tree[root].r,n);
			return ret==-1?root:ret;
			}
		else
			return root;
		}
	}

int main(){
	int m;
	while(scanf("%d",&m)&&m!=0){

		for (int i=0;i<m;++i)
			scanf("%d",&num[i]);
		Main_Maketree(num,m);
		last=0 ;
		preorder(0);
		int n;
		scanf("%d",&n);
		for (int i=0;i<n;++i){
			int que;
			scanf("%d",&que);
			int res=findID(0,que);
			if(res == -1)
				printf("-1\n");
			else
				printf("%d %d\n",Tree[res].num,index[res]);
			}
		printf("\n");
		}
	return 0;
	}