QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#732055 | #9574. Strips | Lzy_# | WA | 24ms | 3584kb | C++14 | 1.7kb | 2024-11-10 12:54:24 | 2024-11-10 12:54:24 |
Judging History
answer
#include <bits/stdc++.h>
void solve() {
int n, m, k, w;
std::cin >> n >> m >> k >> w;
std::vector<int> a(n + 1);
for (int i = 1; i <= n; ++ i) {
std::cin >> a[i];
}
std::vector<int> b(m + 3);
b[1] = 0, b[m + 2] = w + 1;
for (int i = 2; i <= m + 1; ++ i) {
std::cin >> b[i];
}
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
int cur = 0;
std::vector<int> ans;
for (int i = 1; i <= m + 1; ++ i) {
int l = b[i], r = b[i + 1];
std::vector<int> g;
while (cur < n && a[cur + 1] > l && a[cur + 1] < r) {
cur ++;
g.push_back(a[cur]);
}
if (!g.size()) {
continue;
}
std::vector<int> f;
int lmin = r, pos = -1;
for (int j = g.size() - 1; j >= 0; -- j) {
if (g[j] >= lmin) {
continue;
} else {
if (g[j] - l < k) {
pos = j;
break;
}
f.push_back(g[j]);
lmin = g[j] - k + 1;
}
}
if (pos == -1) {
for (auto j : f) {
ans.push_back(j - k + 1);
}
} else {
ans.push_back(l + 1);
int rmax = l + k;
if (rmax >= r) {
std::cout << -1 << '\n';
return ;
}
reverse(f.begin(), f.end());
for (auto j : f) {
int lpos = j - k + 1;
if (lpos < rmax) {
ans.push_back(rmax + 1);
rmax = rmax + k;
if (rmax >= r) {
std::cout << -1 << '\n';
return ;
}
} else {
ans.push_back(lpos);
rmax = lpos + k - 1;
}
}
}
}
std::cout << ans.size() << '\n';
for (auto i : ans) {
std::cout << i << ' ';
}
std::cout << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0); std::cout.tie(0);
int T;
std::cin >> T;
while (T --) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3564kb
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 1 6 9 14 -1 2 1 4 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 24ms
memory: 3584kb
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 2 32 7 4 3 14 22 40 36 28 3 22 46 64 8 7 1 24 20 30 36 54 63 3 3 14 30 6 1 7 11 30 41 47 4 14 27 34 47 2 65 42 1 27 1 9 1 62 5 24 42 33 60 47 2 3 31 3 11 19 29 3 2 15 33 3 30 25 42 3 2 17 59 4 1 11 21 32 2 65 53 3 49 58 65 3 60 43 78 1 78 4 1 11 15 21 5 3 7 17 36 48 2 1 44 ...
result:
wrong answer There are more than one stripe covering cell 11 (test case 42)