QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #791877 | #9574. Strips | moqizhu2005 | TL | 0ms | 3760kb | C++14 | 1.8kb | 2024-11-28 21:33:49 | 2024-11-28 21:33:49 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<bitset>
#include<stack>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pa;
#define mk make_pair
const ll maxn=1000005,inf=(1ll<<60);
inline ll read(){
ll w=0,h=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')h=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){w*=10;w+=ch-'0';ch=getchar();}
return w*h;
}
vector<ll> ans;
vector<ll> a,b;
int main(){
ll T=read();
while(T--){
ll n=read(),m=read(),k=read(),w=read();
ans.clear();
for(int i=1;i<=n;i++){
ll x=read();
a.push_back(x);
}
for(int i=1;i<=m;i++){
ll x=read();
b.push_back(x);
}
sort(a.begin(),a.end());
sort(b.begin(),b.end());
ll now=1;
while(now<=w){
ll pos=lower_bound(a.begin(),a.end(),now)-a.begin();
//cout<<"!"<<now<<" "<<pos<<" "<<a[pos]<<endl;
ans.push_back(a[pos]);
if(a[pos]<now) break;
now=a[pos]+k;
}
bool is=1;
for(int i=ans.size()-1;i>=0;i--){
if(i<(int)ans.size()-1&&ans[i+1]-ans[i]<k){
ans[i]=ans[i+1]-k;
if(ans[i]<=0){is=0;break;}
ll pos=upper_bound(b.begin(),b.end(),ans[i])-b.begin();
if(ans[i]>=b[pos]) continue;
if(b[pos]-ans[i]<k){is=0;break;}
continue;
}
if(i==(int)ans.size()-1&&w+1-ans[i]<k) ans[i]=w+1-k;
ll pos=upper_bound(b.begin(),b.end(),ans[i])-b.begin();
if(ans[i]>=b[pos]) continue;
if(b[pos]-ans[i]<k) ans[i]=b[pos]-k;
if(ans[i]<=0){is=0;break;}
}
if(!is) printf("-1\n");
else{
printf("%lld\n",(ll)ans.size());
for(int i=0;i<(int)ans.size();i++) printf("%lld ",ans[i]);
printf("\n");
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
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
Time Limit Exceeded
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:
-1 -1 -1 12 1 7 13 21 24 31 35 38 53 58 63 66 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 52 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 22 23 25 26 27 28 29 30 31 32 33 34 36 37 38 40 41 42 43 44 48 49 50 51 52 53 54 55 58 59 60 61 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...