QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#755654 | #9574. Strips | nodnodnod123 | RE | 0ms | 3504kb | C++14 | 1.9kb | 2024-11-16 17:50:03 | 2024-11-16 17:50:03 |
Judging History
answer
#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
const int N = 2e5 + 10, INF = 0x3f3f3f3f;
//int cnt[N];
void solve() {
ll n, m, k, w; cin >> n >> m >> k >> w;
set<ll>v1;//red
vector<ll>v2;//black
vector<ll>ans;//答案数组
ll x; v2.push_back(0); v2.push_back(w + 1);//边界
for (ll i = 0; i < n; ++i) {
cin >> x; v1.insert(x);
}
for (ll i = 0; i < m; ++i) {
cin >> x; v2.push_back(x);
}
sort(v2.begin(), v2.end());
//处理每区间
ll le = 0; auto rit = v1.begin();//区间左黑边界下标,红格子指针
while (le <= v2.size() - 2) {
ll lef = v2[le], rig = v2[le + 1];
if (lef == rig - 1) { le++; continue; }
//ll sta = lef + 1;
ll bered =0;//上一个红格子的位置
while (rit!=v1.end()&&*rit < rig) {
if (*rit - bered >= k||rit==v1.begin()) {
ans.push_back(*rit);
//cout << *rit << "push" << endl;
bered = *rit;
}
rit++;
}
//cout << bered <<"bred"<< rig<<endl;
if (bered+k-1 >= rig) {//需要左移每个区间
ans[ans.size() - 1] -= bered+k- rig;
//cout << ans[ans.size() - 1] << "change" << endl;
if (ans[ans.size() - 1] <= lef) { cout << -1 << endl; return; }
//查看是否区间重叠
for (ll i = ans.size() - 1; i - 1 >= 0 && ans[i - 1] > lef; --i) {
ll zuo = ans[i];//每个小区间的左边界
ll szuo = ans[i - 1];
//cout << ans[i - 1] << "ans[i-1]" << lef << endl;
if (zuo - szuo < k) {
ans[i - 1] -= k - (zuo - szuo);//左移上一个区间
}
if (ans[i - 1] <= lef) { cout << -1 << endl; return; }
}
}
//if (sta <= lef) { cout << -1 << endl; return; }
le++;
}
cout << ans.size() << endl;
for (ll i = 0; i < ans.size(); ++i) { cout << ans[i] << " "; }
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3504kb
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
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...
output:
2 3 32 7 3 4 14 22 28 36 40