QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176275 | #5378. 匹配问题 | Ustinian26 | 0 | 137ms | 263924kb | C++20 | 2.6kb | 2023-09-11 14:25:38 | 2023-09-11 14:25:40 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
int x=0;char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return x;
}
const int N=5e5+3;
int n,A,B,a[N],b[N],id[N<<2];
int tot=-1,h[N*3],cnt,S,T;
struct edge{int v,w,f,nxt;}e[N<<6];
inline void add(int u,int v,int w,int f) {e[++tot]={v,w,f,h[u]},h[u]=tot;}
inline void lnk(int u,int v,int w,int f) {add(u,v,w,f),add(v,u,0,-f);}
#define mid ((l+r)>>1)
#define ls (x<<1)
#define rs (x<<1|1)
inline void bil(int x=1,int l=1,int r=n)
{
id[x]=++cnt;
if(l==r) return lnk(id[x],T,1,0);
bil(ls,l,mid),lnk(id[x],id[ls],mid-l+1,0);
bil(rs,mid+1,r),lnk(id[x],id[rs],r-mid,0);
}
inline void Lnk(int k,int L,int R,int f,int x=1,int l=1,int r=n)
{
if(L<=l&&r<=R) return lnk(k,id[x],1,f);
if(L<=mid) Lnk(k,L,R,f,ls,l,mid);
if(R>mid) Lnk(k,L,R,f,rs,mid+1,r);
}
int mxw,mxf,d[N*3],cur[N*3];
bool vis[N*3];
deque<int> q;
inline bool chx(int &x,int y) {return x<y?(x=y,1):0;}
inline bool spfa()
{
for(int i=1;i<=cnt;++i) d[i]=-N,cur[i]=h[i];
d[T]=0,q.push_front(T);
while(!q.empty())
{
int u=q.front();q.pop_front();
vis[u]=0;
for(int i=h[u],v;~i;i=e[i].nxt)
{
v=e[i].v;
if(!e[i].w||!chx(d[v],d[u]+e[i].f)||vis[v]) continue;
vis[v]=1;
if(!q.empty()&&d[v]>d[q.front()]) q.push_front(v);
else q.push_back(v);
}
}
return d[S]>-N;
}
inline int dfs(int u=S,int flow=N)
{
if(u==T) return (mxf+=d[T]*flow),flow;
int rmn=flow;
vis[u]=1;
for(int i=cur[u],v;~i&&rmn;i=e[i].nxt)
{
cur[u]=i,v=e[i].v;
if(!vis[v]&&e[i].w&&d[u]+e[i].f==d[v])
{
int c=dfs(v,min(rmn,e[i].w));
rmn-=c,e[i].w-=c,e[i^1].w+=c;
}
}
vis[u]=0;
return flow-rmn;
}
int main()
{
// freopen("match.in","r",stdin);
// freopen("match.out","w",stdout);
memset(h,-1,sizeof(h));
n=read(),A=read(),B=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) b[i]=read();
sort(a+1,a+n+1),sort(b+1,b+n+1);
S=++cnt,T=++cnt,bil();
for(int i=1,x=1,y=1,z=1;i<=n;++i)
{
while(x<=n&&b[x]<a[i]) ++x;
while(y<=n&&b[y]<=a[i]+A-B) ++y;
while(z<=n&&b[z]<=a[i]+A) ++z;
lnk(S,++cnt,1,0);
if(x<y) Lnk(cnt,x,y-1,1);
if(y<z) Lnk(cnt,y,z-1,0);
}
while(spfa()) for(int x;(x=dfs());mxw+=x);
if(mxw<n) puts("-1");
else printf("%d\n",mxf);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 20208kb
input:
2 2 1 1 1 1 1
output:
-1
result:
wrong answer 1st lines differ - expected: '2', found: '-1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Wrong Answer
Test #100:
score: 0
Wrong Answer
time: 137ms
memory: 263924kb
input:
500000 500000 10 200184 74991 71203 334998 316800 34483 120570 301054 331108 232072 189788 397143 490296 56807 361700 88818 42376 460305 371750 450351 338384 429789 426045 445029 152316 408919 188124 144966 457495 475025 225370 260510 383159 495247 54319 246245 240728 372033 439599 119720 449020 451...
output:
-1
result:
wrong answer 1st lines differ - expected: '312193', found: '-1'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%