QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#777987#9574. StripsdoctorZ_WA 0ms5704kbC++142.0kb2024-11-24 11:56:272024-11-24 11:56:28

Judging History

你现在查看的是最新测评结果

  • [2024-11-24 11:56:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5704kb
  • [2024-11-24 11:56:27]
  • 提交

answer

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=2e5+100;
int n,m,k,w;
int a[N+10],b[N+10];
int cnt;
struct node
{
	int v,type;
}p[N+10];
bool cmp(node a,node b)
{
	return a.v<b.v||(a.v==b.v&&a.type<b.type);
}
int f[N+10];
bool check(int x)
{
	if(x<k) return false;
	int l=1,r=m,mid,ans=0;
	while(l<=r)
	{
		mid=l+r>>1;
		if(b[mid]<=x)
			ans=mid,l=mid+1;
		else
			r=mid-1;
	}
	return (ans==0||b[ans]<x-k+1);
}
int pre[N+10],Ans[N+10];
void print(int x)
{
	if(x==0) return;
//	printf("\nx %d\n",x);
	print(pre[x]);
	if(Ans[x]==1)
		printf("%d ",p[x].v-k+1);
}
int main()
{
//	freopen("K.in","r",stdin);
	int T;
	scanf("%d",&T);
	for(;T--;)
	{
		scanf("%d %d %d %d",&n,&m,&k,&w);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=1;i<=m;i++) scanf("%d",&b[i]);
		sort(a+1,a+1+n),sort(b+1,b+1+m);
//		for(int i=1;i<=n;i++) printf("%d ",a[i]);puts("");
//		for(int i=1;i<=m;i++) printf("%d ",b[i]);puts("");
		cnt=0;
		for(int i=1;i<=n;i++)
			p[++cnt]={a[i],0};
		for(int i=1;i<=m;i++)
			if(b[i]+k<=w)
				p[++cnt]={b[i]+k,1};
		p[++cnt]={k,1};
		sort(p+1,p+1+cnt,cmp);
//		printf("cnt %d\n",cnt);
//		for(int i=1;i<=cnt;i++)
//			printf("%d %d\n",p[i].v,p[i].type);
		f[0]=0;
		for(int i=1;i<=cnt;i++)
		{
			f[i]=n+1,pre[i]=0,Ans[i]=0;
			if(p[i].type==1)
				f[i]=min(f[i],f[i-1]),pre[i]=i-1;
			if(check(p[i].v))
			{
				int l=0,r=i-1,mid,ans=0;
				while(l<=r)
				{
					mid=l+r>>1;
					if(p[mid].v<p[i].v-k+1)
						ans=mid,l=mid+1;
					else
						r=mid-1;
				}
				if(f[ans]+1<f[i])
				{
					f[i]=f[ans]+1;
					pre[i]=ans;
					Ans[i]=1;
				}
			}
		}
		if(f[cnt]>n)
		{
			printf("-1\n");
			if(T==11000)
			{
				printf("%d %d %d %d\n",n,m,k,w);
				for(int i=1;i<=n;i++) printf("%d ",a[i]);puts("");
				for(int i=1;i<=m;i++) printf("%d ",b[i]);puts("");
			}
			return 0;
		}
		else
		{
			printf("%d\n",f[cnt]);
			print(cnt),puts(""); 
		}
	}
	return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5704kb

input:

4
5 2 3 16
7 11 2 9 14
13 5
3 2 4 11
6 10 2
1 11
2 1 2 6
1 5
3
2 1 2 6
1 5
2

output:

4
1 6 9 14 
-1

result:

wrong output format Unexpected end of file - int32 expected (test case 3)