QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#749244 | #9574. Strips | ewe | WA | 21ms | 3856kb | C++14 | 2.4kb | 2024-11-14 23:11:34 | 2024-11-14 23:11:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define fopen \
freopen("E:/vscode/oi/in.txt", "r", stdin); \
freopen("E:/vscode/oi/out.txt", "w", stdout);
#define ios \
ios::sync_with_stdio(0); \
cin.tie(0);
#define i64 long long
#define ull unsigned i64
#define pii pair<int, int>
#define pdd pair<double, double>
#define ld long double
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) (x & -x)
#define de(x) cout << #x << " = " << x << '\n'
#define MAXP 20
const int N = 1e5 + 10, M = 1e2 + 10;
const double eps = 1e-12;
const double PI = acos(-1);
bool Mst;
vector<pii> vec;
vector<int> ans;
int n, m, k, d;
void calc(int l, int r, int lim)
{
int len = vec[r].first - vec[l].first + 1, cnt = (len + d - 1) / d;
int delta = cnt * d - len;
int st = max(lim, vec[l].first - delta);
for (int i = 0; i < cnt; i++)
ans.push_back(st + i * d);
}
bool go(int l, int r)
{
int lim = vec[l].first + 1;
for (int i = l + 1; i < r; i++)
{
int ql = vec[i].first;
int j = i;
while (j + 1 < r && vec[j + 1].first - vec[j].first < d)
++j;
calc(i, j, lim);
lim = ans.back() + d;
i = j;
}
if (lim > vec[r].first)
return false;
return true;
}
void solve()
{
cin >> n >> m >> d >> k;
vec.clear();
ans.clear();
for (int i = 0, x; i < n; i++)
{
cin >> x;
vec.push_back({x, 0});
}
for (int i = 0, x; i < m; i++)
{
cin >> x;
vec.push_back({x, 1});
}
vec.push_back({0, 1});
vec.push_back({k + 1, 1});
sort(vec.begin(), vec.end());
for (int i = 1; i <= n + m; i++)
if (vec[i - 1].second == 1 && vec[i].second == 0)
{
int j = i;
while (vec[j].second == 0)
++j;
if (!go(i - 1, j))
{
cout << -1 << '\n';
return;
}
i = j;
}
cout << ans.size() << '\n';
for (int x : ans)
cout << x << ' ';
cout << '\n';
}
bool Med;
signed main()
{
ios;
// fopen;
cerr << (&Med - &Mst) / 1024 / 1024;
int t = 1;
srand(time(0));
cout << fixed << setprecision(12);
cin >> t;
for (int i = 1; i <= t; i++)
{
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3856kb
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 1 6 9 14 -1 2 1 4 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 21ms
memory: 3820kb
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 2 32 7 3 4 14 22 28 36 40 3 22 46 64 8 1 7 20 24 30 36 54 63 3 3 14 30 6 1 7 11 30 41 47 4 14 27 34 47 2 42 65 1 27 1 9 1 62 5 24 33 42 47 60 2 3 31 3 11 19 29 3 2 15 33 3 25 30 42 3 2 17 59 4 1 11 21 32 2 53 65 3 49 58 65 3 43 60 78 1 78 4 1 11 15 21 5 3 7 17 36 48 2 1 44 ...
result:
wrong answer Participant's answer is 3. But jury has a better answer 2. (test case 261)