QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#746858 | #9574. Strips | bhscer | WA | 40ms | 5824kb | C++17 | 2.9kb | 2024-11-14 15:44:20 | 2024-11-14 15:44:22 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
#define fadd(a,b,c) for (int a=b;a<=c;a++)
#define fsub(a,b,c) for (int a=b;a>=c;a--)
#define F first
#define S second
#define CYes cout << "Yes\n"
#define CNo cout << "No\n"
#define CYES cout << "YES\n"
#define CNO cout << "NO\n"
#define println(a) cout << (a) << '\n'
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
void fastIO(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);}
class bhscer {
public:
template<typename FIRST, typename ...PACK> static void debug(FIRST first, PACK... params) { std::cout<< first <<' '; debug(params...);}
template<typename T> static void debug(T end) { std::cout << end << std::endl; }
};
const int N = 5e5;
int a[N], b[N];
void solve() {
int n, m, k, w;
cin >> n >> m >> k >> w;
// map<int,bool> red;
vector<int> all;
map<int,int> allMp;
for (int i=1;i<=n;i++) {
cin >> a[i];
// red[a[i]] = true;
all.push_back(a[i]);
}
m += 2;
b[1] = 0;
b[m] = w+1;
for (int i=2;i<m;i++) {
cin >> b[i];
}
for (int i=1;i<=m;i++) {
// red[b[i]] = false;
all.push_back(b[i]);
}
sort(b+1, b+1+m);
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
for (int i=0;i<all.size();i++) {
allMp[all[i]] = i;
}
vector<int> ans;
bool ok = true;
for (int i=0;i<all.size()-1;) {
// this must be a black.
// find next black.
int nextBIdx = upper_bound(b+1, b+1+m, all[i]) - b;
int nextAllIdx = allMp[b[nextBIdx]];
int wallL = all[i];
int wallR = all[nextAllIdx];
// cout << " here has a range: " << wallL << ' ' << wallR << endl;
int lastCoverTo = 0;
bool success = true;
vector<int> ans1;
for (int j=i+1;j<nextAllIdx;j++) {
if (lastCoverTo >= all[j]) {
continue;
}
if (all[j] + k-1 < wallR) {
lastCoverTo = all[j] + k - 1;
ans1.push_back(all[j]);
continue;
}
// failed to start a cover
// the final part end
// cout << "leftly cover failed" << endl;
success = false;
break;
}
bool successAgain = true;
if (!success) {
ans1.clear();
int preCoverTo = wallR-1 - k + 1;
if (preCoverTo > wallL) {
ans1.push_back(preCoverTo);
for (int j=nextAllIdx-1;j>i;j--) {
if (preCoverTo <= all[j]) {
continue;
}
if (all[j]-k+1 > wallL) {
preCoverTo = all[j]- k + 1;
ans1.push_back(preCoverTo);
continue;
}
successAgain = false;
}
} else {
successAgain = false;
}
}
if (!successAgain) {
ok = false;
break;
}
for (auto j: ans1) {
ans.push_back(j);
}
i = nextAllIdx;
}
if (!ok) {
cout << -1 << '\n';
return;
}
cout << ans.size() << '\n';
for (auto i:ans) {
cout << i << ' ';
}
cout << '\n';
}
signed main() {
fastIO();
int _ = 1; cin >> _;
while (_--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5824kb
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 10 7 14 -1 2 1 5 -1
result:
ok ok 4 cases (4 test cases)
Test #2:
score: -100
Wrong Answer
time: 40ms
memory: 5596kb
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 -1 -1 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 -1 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 2 7 25 1 4 4 9 18 32 29 3 25 27 44...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 6)