QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#747280 | #9574. Strips | kalikari | WA | 47ms | 3804kb | C++17 | 2.8kb | 2024-11-14 16:46:27 | 2024-11-14 16:46:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
/*
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
*/
// #define int long long
#define ld long double
//#define INT __int128
#define eb(x) emplace_back(x)
#define fi first
#define se second
#define sc(x) scanf("%d",&x)
#define SC(x) scanf("%lld",&x)
#define reserve reserve
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const ld eps = 1e-12;
const int N = 2e5 + 10, M = N + 10;
int n,m,k,w;
int red[N];
void solve(){
cin>>n>>m>>k>>w;
set<int>b;
b.insert(0),b.insert(w+1);
for(int i=1;i<=n;i++){
scanf("%d",&red[i]);
}
for(int i=1;i<=m;i++){
int a;
scanf("%d",&a);
b.insert(a);
}
sort(red+1,red+1+n);
vector<int>ans;
int l=0;
while(1){
auto pos=(b.upper_bound(l));
if(pos==b.end())break;
int r=*pos;
// cout<<"____________ "<<l<<" "<<r<<endl;
std::vector<PII> tmp;
int be=upper_bound(red+1,red+1+n,l)-red;
int end=lower_bound(red+1,red+1+n,r)-red;
while(red[end]>=r)end--;
// cout<<"_+++++++++++++++++++++ "<<be<<" "<<end<<endl;
for(int i=be;i<=end;i++){
PII t;
t.first=red[i];
t.second=red[i]+k-1;
// for(;red[i]<=t.second;i++);
while(i<=end&&red[i]<t.second)i++;
tmp.emplace_back(t);
// cout<<"============== "<<t.first<<" "<<t.second<<" "<<i<<" "<<be<<" "<<end<<endl;
}
for(int i=tmp.size()-1;i>=0;i--){
if(tmp[i].second>=r){
int t=tmp[i].second-r+1;
tmp[i].first-=t;
tmp[i].second-=t;
}
else if(i<tmp.size()-1&&tmp[i].second>=tmp[i+1].first){
int t=tmp[i].second-tmp[i+1].first+1;
tmp[i].fi-=t;
tmp[i].second-=t;
}
// cout<<"---------------- "<<tmp[i].first<<" "<<tmp[i].second<<" "<<i<<endl;
// cout<<"22222222222"<<endl;
}
if(tmp.size()>0&&tmp[0].first<=l){
puts("-1");
return;
}
for(auto [f,s]:tmp){
ans.emplace_back(f);
}
l=r;
}
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++){
printf("%d ", ans[i]);
}
printf("\n");
}
signed main(){
// ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
int T=1,cas=1;
cin>>T;
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3804kb
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: 47ms
memory: 3776kb
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 3 32 48 66 6 3 22 31 38 54 65 3 5 15 30 3 1 12 41 3 17 30 49 -1 1 27 -1 -1 -1 -1 -1 3 3 16 33 4 25 30 42 43 3 3 17 60 3 2 21 33 -1 -1 -1 1 81 3 2 11 16 5 3 7 17 36 49 -1 2 7 25 -1 3 9 18 31 -1 4 7 8 36 44 2 7 27 -1 4 8 25 47 57 -1 -1 4 35 43 87 92 4 18 28 43 47 4 4 33 40 47...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 1)