QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#778000#9574. StripsdoctorZ_WA 50ms11884kbC++141.8kb2024-11-24 12:01:082024-11-24 12:01:09

Judging History

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

  • [2024-11-24 12:01:09]
  • 评测
  • 测评结果:WA
  • 用时:50ms
  • 内存:11884kb
  • [2024-11-24 12:01:08]
  • 提交

answer

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+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()
{
	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},p[++cnt]={a[i]+k,1};
		for(int i=1;i<=m;i++)
		{
			if(b[i]+k<=w)
				p[++cnt]={b[i]+k,1};
			p[++cnt]={b[i]-1,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");
		}
		else
		{
			printf("%d\n",f[cnt]);
			print(cnt),puts(""); 
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 11824kb

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
2
1 4 
-1

result:

ok ok 4 cases (4 test cases)

Test #2:

score: -100
Wrong Answer
time: 50ms
memory: 11884kb

input:

11000
3 8 2 53
32 3 33
35 19 38 20 1 30 10 6
7 10 1 42
3 14 4 36 28 40 22
17 20 12 41 27 7 1 19 13 9
6 6 13 78
55 76 53 32 54 58
62 45 21 4 7 61
8 7 3 68
9 26 54 31 22 3 38 65
34 16 58 47 52 29 53
5 8 4 33
33 5 30 6 15
27 12 9 28 19 2 13 10
6 1 2 48
8 12 48 1 41 31
40
7 6 7 61
20 19 30 52 49 17 40
3...

output:

2
2 32 
7
3 4 14 22 28 36 40 
3
22 46 64 
8
1 7 20 24 30 36 54 63 
3
3 14 30 
6
1 7 11 30 41 47 
4
14 27 34 47 
2
42 65 
1
27 
1
9 
1
62 
5
24 33 42 47 60 
2
3 31 
3
11 20 29 
3
2 15 33 
3
25 30 42 
3
2 17 59 
-1
2
53 65 
3
49 58 65 
3
43 60 78 
1
78 
4
1 11 15 21 
5
3 7 17 36 48 
2
1 44 
2
7 25 
1
...

result:

wrong answer Participant didn't find a solution but the jury found one. (test case 18)