QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#764697 | #9574. Strips | eastcloud | WA | 34ms | 9688kb | C++17 | 1.9kb | 2024-11-20 10:15:12 | 2024-11-20 10:15:12 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define pi pair<int,int>
#define vi vector<int>
#define cpy(x,y,s) memcpy(x,y,sizeof(x[0])*(s))
#define mset(x,v,s) memset(x,v,sizeof(x[0])*(s))
#define all(x) begin(x),end(x)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ary array
#define eb emplace_back
#define IL inline
using namespace std;
#define N 500005
int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar();
while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*f;
}
void write(int x){
if(x<0)x=-x,putchar('-');
if(x/10)write(x/10);
putchar(x%10+'0');
}
int f[N],a[N],g[N],pre[N];
map<int,int> t;
set<int> S,B;
void solve(){
int n=read(),m=read(),k=read(),w=read();B.clear();S.clear();t.clear();
B.insert(0);B.insert(w+1);
for(int i=1;i<=n;i++)a[i]=read(),S.insert(a[i]);
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)t[a[i]]=i;
for(int i=1,p=0;i<=m;i++)p=read(),B.insert(p);
for(int i=1;i<=n;i++)f[i]=-1;
for(int i=1;i<=n;i++){
auto it=B.lower_bound(a[i]);
int R=(*it)-1,L=(*prev(it))+1;
if(R-L+1<k)return write(-1),putchar('\n'),void();
R=min(R-k+1,a[i]);L=max(L,a[i]-k+1);
int pos=t[*(S.lower_bound(L))];
if(f[pos-1]==-1 || (pos-1!=0 && g[pos-1]+k-1>L))continue;
f[i]=f[pos-1]+1;g[i]=L;pre[i]=pos-1;
//cerr<<i<<' '<<g[i]<<' '<<a[i]<<' '<<f[i]<<' '<<pre[i]<<endl;
}
if(f[n]==-1)return write(-1),putchar('\n'),void();
write(f[n]);putchar('\n');
int u=n;vi res;
while(u){
res.pb(g[u]);u=pre[u];
}
reverse(all(res));
for(auto v:res)write(v),putchar(' ');putchar('\n');
}
int main(){
#ifdef EAST_CLOUD
freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
#endif
int T=read();while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9688kb
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: 34ms
memory: 7748kb
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 -1 3 2 15 33 3 25 30 42 3 2 17 59 -1 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 2 7 25 1 4 4 9 18...
result:
wrong answer Participant didn't find a solution but the jury found one. (test case 14)