QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#753144 | #9574. Strips | xDarkbluex# | RE | 0ms | 0kb | C++17 | 1.5kb | 2024-11-16 11:30:33 | 2024-11-16 11:30:33 |
answer
#include<bits/stdc++.h>
#define int long long
#define N 100007
using namespace std;
int T,n,m,k,w;
int a[N],b[N];
int A[N],nA;
int f[N],g[N],use[N];
int q[N],t;
int cal()
{
f[0]=0;
g[0]=A[0];
for(int i=1;i<=nA;i++)
{
int l=0,r=i-1;
while(l<r)
{
int mid=(l+r+1)>>1;
if(A[i]-A[mid]+1>k)
{
l=mid;
}
else
{
r=mid-1;
}
}
int j=l;
f[i]=f[j]+1;
g[i]=max(g[j]+k,A[i]);
use[i]=j;
}
int x=nA;
while(x)
{
q[++t]=g[x]-k+1;
x=use[x];
}
}
void solve()
{
scanf("%lld%lld%lld%lld",&n,&m,&k,&w);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%lld",&b[i]);
}
sort(a+1,a+n+1);
sort(b+1,b+m+1);
t=0;
b[0]=0;
b[m+1]=w+1;
int j=1,ans=0;
for(int i=1;i<=m+1;i++)
{
A[0]=b[i-1];
nA=0;
while(j<=n&&a[j]<=b[i])
{
A[++nA]=a[j];
j++;
}
cal();
if(g[nA]<b[i])
{
ans+=f[nA];
}
else
{
printf("-1\n");
return ;
}
}
printf("%lld\n",ans);
for(int i=1;i<=t;i++)
{
printf("%lld ",q[i]);
}
printf("\n");
}
signed main()
{
cin>>T;
while(T--)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
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