QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#761970 | #9574. Strips | 123BVN | ML | 0ms | 0kb | C++23 | 2.1kb | 2024-11-19 11:59:38 | 2024-11-19 11:59:40 |
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N = 2e6 + 10;
const int mod = 1e9 + 7;
int a[N], b[N];
queue<int>ans;
deque<int>q[N];
void solve() {
int n, m, len, w;
cin >> n >> m >> len >> w;
for (int i = 1; i <= n; i++)cin >> a[i];
sort(a + 1, a + 1 + n);
for (int i = 1; i <= m; i++)cin >> b[i];
sort(b + 1, b + 1 + m);
while (!ans.empty())ans.pop();
b[0] = 0;
b[m + 1] = w + 1;
int posa = 1;
for (int i = 0; i <= m; i++) {
while (!q[i].empty())q[i].pop_back();
int l, r;
l = b[i];
r = b[i + 1];
while (posa <= n && l < a[posa] && a[posa] < r) {
q[i].push_back(a[posa]);
posa++;
}
}
for (int i = 0; i <= m; i++) {
int l, r;
l = b[i];
r = b[i + 1];
deque<int>list;
int poslen=l;
while (!q[i].empty()) {
int it=q[i].front();
q[i].pop_front();
if(it<=poslen)continue;
else {
poslen=it+len-1;
list.push_back(it);
}
}
if(poslen>=r&&list.size()*len>r-l+1-2){
cout<<-1<<endl;
return;
}
else {
if(list.empty())continue;
if(poslen>=r)poslen=r-len;
else poslen=list.back();
ans.push(poslen);
list.pop_back();
while(!list.empty()){
int pos=list.back();
list.pop_back();
if(pos+len-1>=poslen){
pos=poslen-len;
poslen=pos;
}
ans.push(pos);
}
}
}
cout<<ans.size()<<endl;
while(!ans.empty()){
cout<<ans.front()<<" ";
ans.pop();
}
cout<<endl;
}
signed main() {
int _ = 1;
cin >> _;//cout << "okk" << endl;
while (_--) {
solve();
}
}
/*
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
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
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 10 7 14 -1 2 1 5 -1