QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#773075 | #9574. Strips | RUOHUI | WA | 28ms | 3868kb | C++20 | 2.2kb | 2024-11-23 00:37:07 | 2024-11-23 00:37:09 |
Judging History
answer
#include "bits/stdc++.h"
#define int long long
#define ull unsigned long long
#define PII pair<int, int>
#define TIII tuple<int, int, int>
#define LL __int128
#define eps 1e-6
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
constexpr int N = 2e6 + 10, M = 2e6 + 10, mod = 1e9 + 7, inf = 1e18;
int n, m;
void solve()
{
int k, w;
cin >> n >> m >> k >> w;
// cout << n << " " << m << " " << k << " " << w << endl;
vector<int> a(n + 1), b(m + 2);
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= m; i ++) cin >> b[i];
b[m + 1] = w + 1;
sort(a.begin() + 1, a.end());
sort(b.begin() + 1, b.end());
vector<int> ans;
int solved = 0; //待处理
for(int i = 0; i <= m; i ++)
{
if(solved == n) break;
int l = solved + 1, r = l;
if(b[i + 1] < a[solved]) continue;
//b]i] 和 b[i + 1] 之间的红格子
while(r + 1 <= n && a[r + 1] > b[i] && a[r + 1] < b[i + 1])
{
r ++;
}
// cout << l << " " << r << endl;
vector<int> pos;
for(int j = l; j <= r; j ++)
{
if(pos.empty() || a[j] > pos.back() + k - 1) pos.emplace_back(a[j]);
}
pos.emplace_back(b[i + 1]);
for(int j = pos.size() - 2; j >= 0; j--)
{
if(pos[j] + k - 1 >= pos[j + 1])
{
pos[j] = pos[j + 1] - k;
}
}
if(pos[0] <= b[i]) return cout << -1 << endl, void();
for(int j = 0; j < pos.size() - 1; j++)
{
ans.emplace_back(pos[j]);
}
solved = r;
}
cout << ans.size() << endl;
for(int i = 0; i < ans.size(); i ++)
{
cout << ans[i] << " \n"[i == ans.size() - 1];
}
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << fixed << setprecision(2);
#ifndef ONLINE_JUDGE
freopen("in.txt", "rt", stdin);
freopen("out.txt", "wt", stdout);
#endif
int Cases = 1;
cin >> Cases;
while (Cases--)
{
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
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: 28ms
memory: 3856kb
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:
-1 -1 -1 8 3 9 22 26 31 38 49 55 -1 6 1 8 12 31 41 47 -1 -1 -1 -1 1 5 6 1 24 34 43 48 60 2 4 31 3 2 20 31 -1 3 3 30 40 -1 4 1 11 21 33 2 33 66 -1 4 3 51 62 78 2 3 81 4 2 11 16 23 -1 3 1 16 45 -1 -1 -1 3 4 26 44 -1 -1 -1 -1 1 38 -1 5 14 36 43 87 92 -1 5 4 12 33 41 47 -1 -1 -1 -1 4 1 7 13 36 1 20 -1 -...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 1)