记录编号	29667	评测结果	AAAAAA
题目名称	[POJ 1442] 黑盒子	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.742 s
提交时间	2011-10-25 13:41:22	内存使用	0.61 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[30003],b[30003],m,n,ji=1,q[30002],ji1=0;
int mid(int i,int j,int x);
int main()
{
	freopen ("blackbox.in","r",stdin);
	freopen ("blackbox.out","w",stdout);
	scanf("%d%d",&m,&n);
	for (int i=1;i<=m;i++)
	{
		scanf("%d",&a[i]);
	}
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&b[i]);
	}
	q[0]=0;
	for (int i=1;i<=m;i++)
	{
		if (ji1==0)
		{
			q[i]=a[i];
			ji1++;
		}
		else
		{
			int temp;
			temp=mid(1,ji1,i);
			if (a[i]>q[ji1])
			{
				q[ji1+1]=a[i];
			}
			else
			{
				for (int k=ji1+1;k>=temp;k--)
				{
					q[k]=q[k-1];
				}
				q[temp]=a[i];
			}
			ji1++;
		}
		for (int o=ji;o<=n;o++)
		{
			if (b[o]==i)
			{
				cout<<q[o]<<endl;
				ji=o;
			}
			if (b[o]>i)
			{
				break;
			}
		}
	}
	return 0;
}
int mid(int i,int j,int x)
{
	if (i==j)
	{
		return i;
	}
	if (q[(i+j)/2]==a[x])
	{
		return (i+j)/2;
	}
	if (q[(i+j)/2]>a[x])
	{
		return (mid(i,(i+j)/2,x));
	}
	else
	{
		return (mid((i+j)/2+1,j,x));
	}
}