QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#729785 | #9574. Strips | ucup-team059# | WA | 27ms | 3856kb | C++20 | 1.5kb | 2024-11-09 17:49:51 | 2024-11-09 17:50:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
using i64 = long long;
#define int i64
using vi = vector<int>;
using pii = pair<int,int>;
void solve() {
int n, m, k, w;
cin >> n >> m >> k >> w;
vi r(n);
for(int i = 0; i < n; i ++)
cin >> r[i];
vi b(m);
for(int i = 0; i < m; i ++)
cin >> b[i];
b.push_back(0), b.push_back(w + 1);
ranges::sort(r);
ranges::sort(b);
auto calc = [k](int n, vi a) -> vi {
vi l , r , lst;
for(auto i : a) {
if(r.empty() or i > r.back()){
l.push_back(i);
r.push_back(i + k - 1);
lst.push_back(i);
}else{
lst.back() = i;
}
}
int R = n;
for(int i = l.size() - 1; i >= 0; i --) {
if(r[i] <= R) break;
if(lst[i] > R) return vi();
r[i] = R;
l[i] = R - k + 1;
R = l[i] - 1;
}
if(l[0] >= 1) return l;
else return vi();
};
vi res, cur;
for(int i = 0, j = 0; i + 1 < b.size() and j < n; i ++) {
cur = vi();
while(j < n and b[i] < r[j] and r[j] < b[i + 1])
cur.push_back(r[j] - b[i]), j ++;
if(cur.empty()) continue;
auto ret = calc(b[i + 1] - b[i] - 1, cur);
if(ret.empty()) {
cout << -1 << "\n";
return;
}
for(auto x : ret)
res.push_back(x + b[i]);
}
cout << res.size() << "\n";
for(auto i : res) assert(1 <= i <= w - k + 1 ), cout << i << " ";
cout << "\n";
return;
}
i32 main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int T;
cin >> T;
while(T --)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
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: 27ms
memory: 3676kb
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 41 47 4 17 30 39 49 2 52 67 1 27 1 22 1 62 5 24 33 43 48 60 2 4 31 3 11 20 31 3 3 16 33 3 25 30 42 3 3 17 60 4 1 11 21 33 2 54 66 3 50 59 65 3 50 62 78 1 81 4 2 11 16 23 5 3 7 17 36 49 2 1 45...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 73)