QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#733964 | #9574. Strips | 20225954# | WA | 29ms | 3544kb | C++20 | 2.9kb | 2024-11-10 22:31:19 | 2024-11-10 22:31:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+5;
#define db(x) cerr<<#x<<(x)<<" \n"
const int N = 2e5+10;
int kth;
void solve(){
// cout<<"Case# "<<++kth<<"\n";
ll n,m,k,w,flag =0;
cin>>n>>m>>k>>w;
k--;
using pli = pair<ll,ll>;
vector<pli > a;
for(int i=1;i<=n;i++){
ll x;cin>>x;
a.push_back({x,0});
}
for(int i=1;i<=m;i++){
ll x;cin>>x;
a.push_back({x,1});
}
a.push_back({0,1});
a.push_back({w+1,1});
sort(a.begin(),a.end());
ll prel = 0,nowl =0,nowr =0,cntsum =0,num,anssum =0,dif =0;
vector<ll> ans,pos;
for(int i=0;i<a.size();i++){
if(a[i].second)pos.push_back(i);
}
for(int i=1;i<pos.size();i++){
ll left = a[pos[i-1]].first,right =a[pos[i]].first;
//响铃黑点的左右边界
cntsum =0,nowr =0,nowl =0,num=0,dif =0;
int idx =pos[i]-1;
// if(a[idx]!=left)cntsum+=a[pos[i]].first-a[idx].first-1;
nowl = a[pos[i]].first;
vector<pli > start_pos;
// db(left),db(right);db(i);
// cout<<"[le,ri ]"<<left<<" "<<right<<"\n";
while(a[idx].first!=left){
num++;nowr = a[idx].first;
cntsum+=nowl-nowr-1;
nowl = nowr-k;
start_pos.push_back({nowl,nowr});
// cout<<"[idx ] "<<a[idx].first<<" nowr "<<nowr<<" nowl "<<nowl<<" \n";
while(a[idx-1].second==0&&a[idx-1].first!=left&&a[idx-1].first>=nowl&&idx>=0){
--idx;//一直向左遍历到第一个点;
// cout<<"idx"<<a[idx].first<<" \n";
}
// cout<<"\n";
idx--;
if(idx<0)break;
// cout<<"ok\n";
}
reverse(start_pos.begin(),start_pos.end());
if(num>0){
if(nowl>left){
anssum+=num;
for(auto [x,y]:start_pos){
ans.push_back(x);
}
}
else if(nowl<=left){
dif = left-nowl+1;
ll presum =0,pre =start_pos[0].first-1;
// cout<<"[dif,cntsum]"<<dif<<" "<<cntsum<<"\n";
if(dif<=cntsum){
for(auto [x,y]:start_pos){
presum+= x-pre-1;
// cout<<"y = "<<x<<" presum "<<presum<<"\n";
ans.push_back(x+max(dif-presum,0ll));
}
}else {
flag =1;
}
}
}
if(flag)break;
}
if(flag){
cout<<-1<<"\n";return;
}
cout<<ans.size()<<"\n";
for(auto x:ans)cout<<x<<" ";cout<<"\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
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: 3544kb
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: 29ms
memory: 3504kb
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 13 29 3 2 15 33 3 25 30 42 3 2 17 59 4 1 6 16 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 There are more than one stripe covering cell 13 (test case 14)