QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#848981#9574. StripslaonongminWA 0ms3572kbC++231.9kb2025-01-09 11:05:082025-01-09 11:05:10

Judging History

你现在查看的是最新测评结果

  • [2025-01-09 11:05:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3572kb
  • [2025-01-09 11:05:08]
  • 提交

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)