QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#737815#9574. Stripsmyy#RE 1ms7680kbC++203.2kb2024-11-12 16:55:172024-11-12 16:55:23

Judging History

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

  • [2024-11-12 16:55:23]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:7680kb
  • [2024-11-12 16:55:17]
  • 提交

answer

#include <iostream> 
#include <vector>
#include<string>
#include<cstring>
#include<map>
#include<stack>
#include<algorithm>
#include<queue>
#include<set>
#include<cstdio>
#include<ctime>
#include<cmath>
#include<unordered_map>
using namespace std;
#define N 500005
#define endl '\n'
#define int long long
#define mod 998244353
#define _(x) cout<<"["<<#x<<"]=["<<x<<"]\n"
int n, m, t, k, q, x, y, z;

void ok() {
    cout << "---ok---\n";
}
void debug(string x,int y) {
    cout << "["<<x<<"]=[" << y<<"]" << endl;
}
void debug(string x, int y[]) {
    cout << "[" << x << "] = [";
    for (int i = 0; i < 10; i++)cout << y[i] << " ";
    cout << "]" << endl;
}
void debug(string x, vector<int>y) {
    cout << "[" << x << "] = [";
    for (auto i : y)cout << i << " ";
    cout << "]" << endl;
}
void debug(string x, map<int, int>y) {
    cout << "[" << x << "] = [";
    for (auto [i, j] : y)cout << "(" << i << "," << j << ") ";
    cout << "]" << endl;
}

int a[N];
int dp[N];
int fa[N];
vector<int>v;

int dfs(int L, int R) {
    if (L > R)return 1;
    x = 0, y = 0;
    for (int i = L;i <= R;i++) {
        if (a[i] == 1) {
            if (x == 0)x = i;
            y = i;
        }
    }
   /* cout << "@" << L << " " << R << endl;
    _(x);_(y);_(k);*/
    if ((y - x + 1 + k - 1) / k * k > (R - L + 1)) {
        return 0;
    }

    for (int i = L;i <= R;i++) {
        dp[i] = 0;fa[i] = 0;
    }
    dp[L - 1] = 0;
    for (int i = L;i <= R-k+1;i++) {
        if (i == R - k + 1) {
            if (y >= R - k + 1)dp[i] = dp[i - 1] + 1;
            break;
        }
        if (a[i] == 1) {
            if (i - k >= L) {
                dp[i] = dp[i - k] + 1;
                fa[i] = fa[i - k];
            }
            else dp[i] = 1,fa[i]=i;
        }
        else {
            dp[i] = dp[i - 1],fa[i]=fa[i-1];
        }
    }
    x = 1;
    for (int i = L;i <= R;i++) {
        if (dp[i] == x)v.push_back(i), x++;
    }
    return 1;

}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int test = 1;
    cin >> test;
    while (test--) {
        int w;
        int flag = 1;
        v.clear();
        cin >> n >> m >> k >> w;
        for (int i = 1;i <= w;i++)a[i] = 0;
        for (int i = 1;i <= n;i++) {
            cin >> t;
            a[t] = 1;
        }
        for (int i = 1;i <= m;i++) {
            cin >> t;
            a[t] = -1;
        }
        int ans = 0;
        int la = 1;
        a[w + 1] = -1;
        for (int i = 1;i <= w+1;i++) {
            if (a[i] == -1) {
                if (dfs(la, i - 1)) {
                    la = i + 1;
                }
                else {
                    flag = 0;
                }
            }
        }
   //     ok();
        if (flag) {
            cout << v.size() << endl;
            for (auto i : v)cout << i << " ";
            cout << endl;
        }
        else cout << -1 << endl;

    }
    return 0;
}

/*
 5
 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

 4 1 2 9
 1 4 5 8
 9
*/


/*
 4
 6 2 14 9 

 -1

 2
 1 4

 -1

 3
 1 4 7


*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 7680kb

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
Runtime Error

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:

3
3 32 33 
7
3 4 14 22 28 36 40 
-1
8
3 9 22 26 31 38 54 65 
-1
6
1 8 12 31 41 47 
-1
-1
-1
-1
-1
5
24 33 43 48 60 
-1
3
11 20 31 
-1
3
25 30 42 
-1
4
2 15 21 33 
2
54 66 
-1
-1
1
81 
4
2 11 16 23 
-1
-1
-1
-1
4
9 18 31 32 
-1
3
7 8 36 
-1
-1
-1
-1
-1
4
35 43 87 92 
-1
-1
-1
-1
7
11 31 36 42 54 58 8...

result: