QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#775843#9574. StripspoetryfactoryWA 23ms3876kbC++204.6kb2024-11-23 16:50:552024-11-23 16:50:55

Judging History

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

  • [2024-11-23 16:50:55]
  • 评测
  • 测评结果:WA
  • 用时:23ms
  • 内存:3876kb
  • [2024-11-23 16:50:55]
  • 提交

answer

// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#define INF 0x3fffffff
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e, ...) e
#define all1(x) (x).begin(), (x).end()
#define all2(x, i) (x).begin() + (i), (x).end()
#define all3(x, i, j) (x).begin() + (i), (x).begin() + (j)
#define all(...) overload3(__VA_ARGS__, all3, all2, all1)(__VA_ARGS__)
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define eb emplace_back
#define mkp make_pair
#define lowbit(x) (x & -x)
#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = (a); i < ll(b); ++i)
#define FOR4(i, a, b, c) for (ll i = a; i < ll(b); i += (c))
#define REP1(a) for (ll _ = 1; _ <= a; ++_)
#define REP2(i, a) for (ll i = 1; i <= ll(a); ++i)
#define REP3(i, a, b) for (ll i = (a); i <= ll(b); ++i)
#define REP4(i, a, b, c) for (ll i = (a); i <= ll(b); i += (c))
#define PER(i, a, b) for (ll i = (a); i >= ll(b); --i)
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define REP(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
#define MT       \
    int tt;      \
    cin >> tt;   \
    while (tt--) \
    {            \
        solve(); \
    }
#define suffZero(x) (__builtin_ctz(x))
#define suffZeroll(x) (__builtin_ctzll(x))
#define preZero(x) (__builtin_clz(x))
#define preZeroll(x) (__builtin_clzll(x))
#define countOne(x) (__builtin_popcount(x))
#define countOnell(x) (__builtin_popcountll(x))
#define lastOne(x) (__builtin_ffs(x))
#define firstOne(x) (32 - preZero(x))
#define firstOnell(x) (64 - preZeroll(x))
#ifdef LOCAL
#include "dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vector<pii>> vvpii;
typedef vector<vector<int>> vvi;
mt19937_64 rng{chrono::steady_clock::now().time_since_epoch().count()};
#define endl '\n'
vvi dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}};

void solve()
{
    int n, m, k, w;
    cin >> n >> m >> k >> w;
    vi a(n + 1), b(m + 1);
    REP(i, 1, n)
    {
        cin >> a[i];
    }
    REP(i, 1, m)
    {
        cin >> b[i];
    }
    b.eb(0);
    b.eb(w + 1);
    sort(all(a, 1));
    sort(all(b, 1));
    vi res(1);
    int r = 0;
    REP(i, 1, n)
    {
        if (r >= a[i])
            continue;
        int c = 0;
        auto it = upper_bound(all(b, 1), a[i]);
        if (it == b.end())
        {
            res.eb(a[i]);
            r = a[i] + k - 1;
            continue;
        }
        else
        {
            c = *it;
            if (c > a[i] + k - 1)
            {
                res.eb(a[i]);
                r = a[i] + k - 1;
                continue;
            }
            else
            {
                if (it != b.begin() && c - *(it - 1) <= k)
                {
                    cout << -1 << endl;
                    return;
                }
                else
                {
                    res.eb(c - k);
                    r = c;
                    continue;
                }
            }
        }
    }
    int siz = sz(res) - 1;
    vi valid(siz + 1, 1);
    PER(i, siz, 2)
    {
        if (valid[i] == 0)
            continue;
        if (res[i] <= res[i - 1])
            valid[i - 1] = 0;
        if (res[i - 1] + k - 1 >= res[i])
        {
            int lb = 0;
            auto it = upper_bound(b.rbegin(), b.rend(), res[i], greater<int>());
            if (it != b.rbegin())
                lb = *it;
            if (lb > res[i] - k)
                res[i - 1] = lb - k;
            else
                res[i - 1] = res[i] - k;
            if (res[i - 1] < 1)
            {
                cout << -1 << endl;
                return;
            }
        }
    }
    cout << accumulate(all(valid, 1), 0) << endl;
    REP(i, 1, sz(res) - 1)
    {
        if (valid[i])
            cout << res[i] << " ";
    }
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    clock_t st = clock();
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    //-------------------------------------
    MT;
//-------------------------------------
#ifdef LOCAL
    cerr << "Time:" << clock() - st << "ms\n";
#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3672kb

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: 23ms
memory: 3876kb

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
3 32 
7
3 4 14 22 28 36 40 
3
32 48 66 
8
3 9 22 26 31 38 54 65 
3
5 15 30 
6
1 8 12 31 41 47 
4
17 30 39 49 
2
52 67 
1
27 
1
22 
1
62 
5
24 33 43 48 60 
2
4 31 
3
11 20 31 
3
3 16 33 
3
25 30 42 
3
3 17 60 
4
1 11 21 33 
2
54 66 
3
50 59 65 
3
50 62 78 
1
81 
4
2 11 16 23 
5
3 7 17 36 49 
2
1 45...

result:

wrong answer There is at least one stripe covering black cell 1 (test case 92)