QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#728786 | #9574. Strips | ucup-team5296# | WA | 25ms | 4144kb | C++20 | 1.8kb | 2024-11-09 15:55:13 | 2024-11-09 15:55:33 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define eb emplace_back
#define ep emplace
#define pii pair<int,int>
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define mems(arr,x) memset(arr,x,sizeof(arr))
#define memc(arr1,arr2) memcpy(arr1,arr2,sizeof(arr2))
using namespace std;
const int maxn=1e5+10,V=2e9;
int n,m,k,w,ans;
int a[maxn],b[maxn];
vector<int> v[maxn],out;
bool solve(int x){
// printf("v[%d] : ",x);for(int i:v[x]) printf("%d ",i);puts("");
bool flag=true;
vector<pii> vec;vec.clear();
for(int i=0;i<v[x].size();i++){
int l=v[x][i];
// printf("i = %d [%d,%d]\n",i,l,l+k);
ans++;
vec.eb(l,l+k-1);
if(l+k-1>=b[x]){flag=false;break;}
else i=lower_bound(v[x].begin(),v[x].end(),l+k)-v[x].begin()-1;
}
if(flag){
for(auto [l,r]:vec) out.eb(l);
return true;
}
// puts("fuck");
int L=b[x]-1;bool ret=false;
for(int i=vec.size()-1;~i;i--){
int l=vec[i].fi,r=vec[i].se;
if(r<=L){ret=true;break;}
r=L;
l=r-k+1;
vec[i]=pii(l,r);
L=l-1;
}
if(L>=b[x-1]) ret=true;
for(auto [l,r]:vec) out.eb(l);
return ret;
}
void matt(){
out.clear();
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+n+1);sort(b+1,b+m+1);
b[0]=0;
b[m+1]=w+1;
for(int i=1;i<=n;i++){
int k=lower_bound(b+1,b+m+2,a[i])-b;
v[k].eb(a[i]);
}
for(int i=1;i<=m+1;i++)
if(!solve(i)) return puts("-1"),void();
printf("%d\n",out.size());
for(int i:out) printf("%d ",i);puts("");
}
int main(){
int T;scanf("%d",&T);while(T--)matt();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3884kb
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 2 7 10 14 -1 2 1 5 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 25ms
memory: 4144kb
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 3 32 8 3 4 14 18 22 28 36 40 -1 13 3 9 3 22 26 31 32 38 49 14 32 55 65 -1 9 3 9 12 31 3 22 26 41 47 -1 -1 -1 -1 -1 13 1 3 7 24 32 34 43 53 55 64 14 30 40 9 3 9 12 16 3 22 41 48 31 -1 -1 12 2 3 3 4 22 30 31 32 36 32 33 42 12 1 3 3 5 28 32 42 47 14 30 40 60 -1 18 3 6 9 15 25 3 22 26 34 31 32...
result:
wrong answer Integer parameter [name=c] equals to 8, violates the range [-1, 7] (test case 2)