QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#775860 | #9574. Strips | poetryfactory | WA | 23ms | 3944kb | C++20 | 4.8kb | 2024-11-23 16:53:06 | 2024-11-23 16:53:06 |
Judging History
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.rend())
lb = *it;
if (lb > res[i] - k)
{
if (it != b.rend() - 1 && lb - *(it + 1) <= k)
{
cout << -1 << endl;
return;
}
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3900kb
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: 3944kb
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)