QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#748448 | #9574. Strips | caojc# | RE | 0ms | 3616kb | C++20 | 3.1kb | 2024-11-14 20:25:45 | 2024-11-14 20:25:47 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define db(args...){\
string _s = #args; replace(_s.begin(), _s.end(), ',', ' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout << '\n';}
void err(istream_iterator<string> it){}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cout << *it << " = " << a << ' ';
err(++it, args...);
}
void solve() {
ll n, m, k, w;
cin >> n >> m >> k >> w;
vector<int> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
b.push_back(0); b.push_back(w + 1);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
bool ok = 1;
vector<int> ans;
auto wk = [&] (vector<int> a, int L, int R) {
a.insert(a.begin(), L);
int n = a.size();
if (n == 1) return;
vector<int> pre(n, -1), pos(n);
pos[0] = L;
for (int i = 1, j = 0; i < n; i++) {
if (i == 1) {
int l = max((ll)L, a[i] - k + 1);
int r = l + k - 1;
if (i + 1 < n && r > a[i + 1]) continue;
if (i == n - 1 && r > R) continue;
pre[i] = 0;
pos[i] = r;
continue;
}
while (a[i] - a[j] + 1 > k) {
j++;
}
assert(j == 0 || pos[j - 1] < a[j]);
int l = max(pos[j - 1] + 1ll, a[i] - k + 1);
int r = l + k - 1;
if (i + 1 < n && r >= a[i + 1]) continue;
if (i == n - 1 && r > R) continue;
pos[i] = l + k - 1;
pre[i] = j - 1;
}
if (pre[n - 1] == -1) {
ok = 0;
} else {
int x = n - 1;
while (pre[x] != -1) {
ans.push_back(pos[x]);
x = pre[x];
}
}
};
for (int i = 1; i < b.size(); i++) {
int x = b[i - 1], y = b[i];
auto p = lower_bound(a.begin(), a.end(), x);
auto q = lower_bound(a.begin(), a.end(), y);
wk(vector<int>(p, q), x + 1, y - 1);
if (!ok) break;
}
if (!ok) {
cout << "-1\n";
return;
}
cout << ans.size() << '\n';
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] - k + 1 << " \n" [i + 1 == ans.size()];
}
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
return 0;
}
/*
g++ 1.cpp -std=c++20 -o 1 && ./1 < in.txt > out.txt
*/
// L
// void pre(int n) {
// vector<int> p(n);
// iota(p.begin(), p.end(), 0);
// db(n);
// do {
// set<int> st;
// for (int i = 0; i < n; i++) {
// st.insert(p[i] ^ i);
// }
// if (st.size() == n) {
// for (auto x : p) cout << x << ' ';
// cout << '\n';
// return;
// }
// } while (next_permutation(p.begin(), p.end()));
// cout << "No\n";
// }
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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 9 6 14 -1 2 1 4 -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...