QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#732502 | #9574. Strips | ucup-team4479# | WA | 23ms | 5884kb | C++23 | 1.8kb | 2024-11-10 14:54:17 | 2024-11-10 14:54:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
constexpr int N=200005;
int n,m,k,w;
int a[N],b[N];
int f[N],g[N],lst[N];
pair<int,vector<int>> calc(int L,int R)
{
int l=lower_bound(a+1,a+n+1,L)-a,r=upper_bound(a+1,a+n+1,R)-a-1;
if(l>r) return make_pair(0,vector<int>());
int res=0;
f[l-1]=0,g[l-1]=L,lst[l-1]=l-1;
for(int i=l;i<=r;i++)
{
if(g[i-1]>=a[i])
{
f[i]=f[i-1],g[i]=g[i-1],lst[i]=lst[i-1];
}
else
{
int pre=lower_bound(a+l,a+r+1,a[i]-k+1)-a-1;
int to=upper_bound(a+l,a+r+1,g[pre])-a-1;
// cerr<<"lst"<<pre<<" "<<g[pre]<<"\n";
f[i]=f[to]+1,g[i]=g[pre]+1+k-1;
lst[i]=to;
}
// cerr<<"find"<<i<<" "<<a[i]<<" "<<f[i]<<" "<<g[i]<<"\n";
}
if(g[r]>=R) return make_pair(-1,vector<int>());
vector<int>pos;
for(int u=r;u>=l;u=lst[u])
pos.emplace_back(g[u]-k+1);//cerr<<"to"<<u<<"\n";
reverse(pos.begin(),pos.end());
// cerr<<"calc"<<L<<" "<<R<<" "<<f[r]<<" "<<g[r]<<'\n';
return make_pair(f[r],pos);
}
void solve()
{
cin>>n>>m>>k>>w;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>b[i];
sort(a+1,a+n+1);
sort(b+1,b+m+1);
b[0]=0;
b[m+1]=w+1;
int ans=0;
vector<int>res;
for(int i=0;i<=m;i++)
{
auto [cnt,pos]=calc(b[i],b[i+1]);
if(cnt==-1)
{
cout<<-1<<"\n";
return;
}
ans+=cnt;
res.insert(res.end(),pos.begin(),pos.end());
}
cout<<ans<<"\n";
for(int u:res)
cout<<u<<" ";
cout<<"\n";
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
int T;
cin>>T;
while(T--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5612kb
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: 23ms
memory: 5884kb
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 31 5 3 14 21 28 30 3 22 46 63 7 1 4 20 30 35 54 59 3 3 14 29 4 1 7 41 43 4 8 27 34 47 1 48 1 18 1 9 1 40 3 10 29 48 2 1 19 3 11 19 29 3 1 9 31 2 6 42 3 1 8 50 4 1 11 21 32 1 52 3 43 53 63 3 42 52 78 1 21 4 1 8 15 18 5 1 7 17 19 39 2 1 43 2 7 25 1 4 3 9 18 25 3 24 26 2...
result:
wrong answer There is no stripe covering red cell 33 (test case 1)