QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#720415#9574. StripsSilverGodlyTL 0ms3600kbC++231.7kb2024-11-07 12:33:132024-11-07 12:33:15

Judging History

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

  • [2024-11-07 12:33:15]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3600kb
  • [2024-11-07 12:33:13]
  • 提交

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 ...

result: