QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#848981 | #9574. Strips | laonongmin | WA | 0ms | 3572kb | C++23 | 1.9kb | 2025-01-09 11:05:08 | 2025-01-09 11:05:10 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 检查是否能覆盖所有红色单元格并计算最少条带数量,同时记录条带起始位置
vector<int> check(vector<int>& red, vector<int>& black, int k, int w) {
int n = red.size();
int m = black.size();
int i = 0;
int strip_count = 0;
int strip_start = -1;
vector<int> strip_starts;
while (i < n) {
if (strip_start == -1) {
strip_start = red[i];
strip_count++;
strip_starts.push_back(red[i]);
}
int right = red[i]+k - 1;
bool valid = true;
for (int j = 0; j < m; j++) {
if (black[j] >= strip_start && black[j] <= right) {
valid = false;
break;
}
}
if (valid) {
// 尝试继续扩展这个条带
while (i + 1 < n && red[i + 1] <= right) {
i++;
}
} else {
// 如果这个条带放置不可行,直接返回空向量表示失败
return vector<int>();
}
i++;
strip_start = -1;
}
return strip_starts;
}
int main() {
int T;
cin >> T;
while (T--) {
int n, m, k, w;
cin >> n >> m >> k >> w;
vector<int> red(n);
for (int i = 0; i < n; i++) {
cin >> red[i];
}
sort(red.begin(), red.end());
vector<int> black(m);
for (int i = 0; i < m; i++) {
cin >> black[i];
}
sort(black.begin(), black.end());
vector<int> result = check(red, black, k, w);
if (result.empty()) {
cout << -1 << endl;
} else {
cout << result.size() << " ";
for (int num : result) {
cout << num << " ";
}
cout << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3572kb
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:
-1 -1 2 1 5 -1
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 1)