QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#720415 | #9574. Strips | SilverGodly | TL | 0ms | 3600kb | C++23 | 1.7kb | 2024-11-07 12:33:13 | 2024-11-07 12:33:15 |
Judging History
answer
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return 1ll * a * b / gcd(a, b); }
ll divCeil(ll x, ll y) { return x / y + (x % y != 0); }
const int MAXN = 2e5 + 5;
const double pi = 3.14159265358979323846;
const ll inf = 1e18;
double eps = 1e-9;
const int maxn = 2e5 + 5;
const int mod = 1e9 + 7;
#define endl "\n"
void solve() {
int n, m, k, w;
cin >> n >> m >> k >> w;
vector<int>col(w + 5);//0 white, 1 red, 2 black
vector<int>dp(w + 5, 1e9);
vector<int>nxt(w + 5, 1e9);
vector<int>vis(w + 5);
vector<int>pre(w + 5);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
col[x] = 1;
}
for (int i = 1; i <= m; i++) {
int x;
cin >> x;
col[x] = 2;
}
for (int i = 1; i <= w; i++) {
pre[i] = pre[i - 1] + (col[i] == 2);
}
dp[0] = 0;
for (int i = 1; i <= w; i++) {
if (col[i] != 1)dp[i] = dp[i - 1];
nxt[i] = i - 1;
if (i < k || pre[i] - pre[i - k])continue;
if (dp[i - k] + 1 < dp[i]) {
nxt[i] = i - k;
vis[i] = 1;
}
dp[i] = min(dp[i], dp[i - k] + 1);
}
int ans = (dp[w] >= 1e9 ? -1 : dp[w]);
cout << ans << endl;
if (ans != -1) {
while (w>0) {
if (vis[w])cout << w - k + 1 << " ";
w = nxt[w];
}
cout << endl;
}
return;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin >> t;
while (t--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3600kb
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 14 9 6 1 -1 2 4 1 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Time Limit Exceeded
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 32 2 7 40 36 28 22 14 4 3 3 64 46 22 8 63 54 36 30 24 20 7 1 3 30 14 3 6 47 41 30 11 7 1 4 47 34 27 14 2 65 42 1 27 1 9 1 62 5 60 47 42 33 24 2 31 3 3 29 19 11 3 33 15 2 3 42 30 25 3 59 17 2 4 32 21 11 1 2 65 53 3 65 58 49 3 78 60 43 1 78 4 21 15 11 1 5 48 36 17 7 3 2 44 1 ...