QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #758208 | #9574. Strips | Rezhou# | WA | 53ms | 7908kb | C++23 | 2.3kb | 2024-11-17 16:46:35 | 2024-11-17 16:46:35 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
int a[N];
int b[N];
vector<int> v[N];
queue<int> ans;
void solve() {
while (!ans.empty())ans.pop();
int n, m, k, w;
cin >> n >> m >> k >> w;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i];
sort(a + 1, a + 1 + n);
sort(b +1, b + 1 + m);
b[0] = 0;
b[m + 1] = w+1;
int posa = 1;
for (int i = 0; i <= m; i++) {
int l, r;
v[i].clear();
l = b[i];
r = b[i + 1];
while (l < a[posa] && a[posa] < r) {
v[i].push_back(a[posa]);
posa++;
}
}
// cout << "ok" << endl;
for (int i = 0; i <= m; i++) {
deque<int> q;
int poslen;
poslen = b[i];
for (int j = 0; j < v[i].size(); j++) {
if (v[i][j] <= poslen) continue;
else {
q.push_back(v[i][j]);
poslen = v[i][j] + k-1;
}
}
// cout << i <<" "<<b[i] <<"ok"<<poslen << endl;
if (poslen >= b[i + 1] && b[i] != b[i + 1]) {
if (b[i + 1] - b[i] - 1 < q.size() * k) {
cout << -1 << endl;
return;
}
else if (!q.empty()) {
q.pop_back();
poslen = b[i + 1] - k;
ans.push(poslen);
while (!q.empty()) {
if (q.back() + k - 1 >= poslen) {
ans.push(poslen + k);
poslen = poslen + k;
}
else
ans.push(q.back());
q.pop_back();
}
}
}
else {
while (!q.empty()) {
ans.push(q.front());
q.pop_front();
}
}
}
cout << ans.size() << "\n";
while (!ans.empty()) {
cout << ans.front() << " ";
ans.pop();
}
cout << "\n";
}
signed main() {
int _ = 1;
cin >> _;
while (_--) {
solve();
}
return 0;
}
/*
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: 100
Accepted
time: 2ms
memory: 7908kb
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
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 53ms
memory: 7700kb
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 7 3 4 14 22 28 36 40 3 32 48 66 8 3 9 22 26 31 38 54 65 3 5 15 30 6 1 8 12 31 47 41 4 17 39 30 49 2 52 67 1 27 -1 1 62 6 24 33 43 64 60 48 -1 4 11 20 31 40 3 3 16 33 8 25 30 42 43 48 60 61 65 3 3 17 60 4 21 31 2 33 2 54 66 3 50 59 65 3 50 62 78 1 81 4 2 11 16 23 5 3 7 17 ...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 10)