QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #50586 | #3040. Container | tricyzhkx | WA | 2ms | 18000kb | C++14 | 4.3kb | 2022-09-27 16:10:49 | 2022-09-27 16:10:52 |
Judging History
answer
# include <bits/stdc++.h>
using namespace std;
int n,s,t,W,H,C,cnt,du[250010],bel[510][510],in[250010],out[250010],a[510][510],h[250010],dis[250010],cur[250010],head[250010],to[500010],edge[500010],flow[500010],cap[500010],nxt[500010],tot=1;
vector<int> G[250010];
char s1[510],s2[510];
bool vis[250010];
struct node
{
int v,w;
node(int _v=0,int _w=0):v(_v),w(_w){}
bool operator<(node a)const{return w>a.w;}
};
struct node2
{
int x,y,dir;// 0 : ·, 1 : | , 2 : —
node2(int _x=0,int _y=0,int _d=0):x(_x),y(_y),dir(_d){}
}b[250010];
int id(int i,int j){return (i-1)*H+j;}
void addedge(int u,int v,int w,int c)
{
to[++tot]=v;
edge[tot]=w;
cap[tot]=c;
nxt[tot]=head[u];
head[u]=tot;
}
void add(int u,int v,int w,int c){addedge(u,v,w,c);addedge(v,u,-w,0);}
void Flow(int i,int f){flow[i]+=f;flow[i^1]-=f;}
void spfa()
{
queue<int> que;
for(int i=1;i<=t;i++) h[i]=1e9,vis[i]=0;
h[s]=0;que.push(s);
while(!que.empty())
{
int u=que.front();que.pop();
vis[u]=0;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i],w=edge[i];
if(cap[i]>flow[i] && h[v]>h[u]+w)
{
h[v]=h[u]+w;
if(!vis[v]) vis[v]=1,que.push(v);
}
}
}
}
bool Dij()
{
priority_queue<node> que;
for(int i=1;i<=t;i++) dis[i]=1e9,vis[i]=0;
dis[s]=0;que.emplace(s,0);
while(!que.empty())
{
node t=que.top();que.pop();
if(vis[t.v]) continue;
int u=t.v;vis[u]=1;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i],w=edge[i]+h[u]-h[v];
if(cap[i]>flow[i] && dis[v]>dis[u]+w) dis[v]=dis[u]+w,que.emplace(v,dis[v]);
}
}
return h[t]+dis[t]<0;
}
int dfs(int u,int minn)
{
if(u==t || !minn) return minn;
vis[u]=1;
int f,ans=0;
for(int &i=cur[u];i;i=nxt[i])
{
int v=to[i],w=edge[i]+h[u]-h[v];
if(cap[i]>flow[i] && dis[v]==dis[u]+w && (f=dfs(v,min(minn,cap[i]-flow[i])))>0)
{
flow[i]+=f;flow[i^1]-=f;
ans+=f;minn-=f;
}
if(!minn) break;
}
vis[u]=0;
return ans;
}
int main()
{
cin>>n>>C;
scanf("%s%s",s1+1,s2+1);
for(int i=1;i<=n;i++) (s1[i]=='1'?W:H)++;
int x=0,y=0;
for(int i=1;i<=n;i++)
if(s1[i]=='1') x++;
else
{
y++;
for(int i=x+1;i<=W;i++) a[i][y]++;
}
x=y=0;
for(int i=1;i<=n;i++)
if(s2[i]=='1') x++;
else
{
y++;
for(int i=x+1;i<=W;i++) a[i][y]--;
}
s=W*H+1;t=s+1;
for(int i=1;i<=W;i++)
for(int j=1;j<=H;j++)
if(a[i][j])
{
if((i+j)&1) add(s,id(i,j),0,1),in[id(i,j)]=tot-1;
else add(id(i,j),t,0,1),out[id(i,j)]=tot-1;
}
for(int i=1;i<=W;i++)
for(int j=1;j<=H;j++)
if(a[i][j] && (i+j)&1)
{
if(a[i-1][j]) add(id(i,j),id(i-1,j),-C-2,1);
if(a[i+1][j]) add(id(i,j),id(i+1,j),-C-2,1);
if(a[i][j-1]) add(id(i,j),id(i,j-1),-C-1,1);
if(a[i][j+1]) add(id(i,j),id(i,j+1),-C-1,1);
}
for(int i=1;i<=W;i++)
for(int j=1;j<=H;j++)if((i+j)&1)
for(int u=id(i,j),k=head[u];k;k=nxt[k])
{
int v=to[k],w=edge[k];
if(cap[k]>flow[k] && w==-C-2)
{
Flow(k,1);Flow(in[u],1);Flow(out[v],1);
break;
}
}
spfa();
while(Dij())
{
for(int i=1;i<=t;i++) cur[i]=head[i],vis[i]=0;
dfs(s,1e9);
for(int i=1;i<=t;i++)
if(dis[i]<1e9) h[i]+=dis[i];
}
for(int i=1;i<=W;i++)
for(int j=1;j<=H;j++)
if(a[i][j] && (i+j)&1)
{
int u=id(i,j),v=0;
for(int k=head[u];k;k=nxt[k])
if(to[k]<s && flow[k]==cap[k])
{
v=to[k];
break;
}
if(v)
{
int ti=(v-1)/H+1,tj=(v-1)%H+1,t=(ti==i?2:1);
b[++cnt]=node2(min(i,ti),min(j,tj),t);
bel[i][j]=bel[ti][tj]=cnt;
}
else b[++cnt]=node2(i,j,0),bel[i][j]=cnt;
}
for(int i=1;i<=W;i++)
for(int j=1;j<=H;j++)
if(a[i][j] && !((i+j)&1) && !bel[i][j])
b[++cnt]=node2(i,j,0),bel[i][j]=cnt;
auto add=[&](int u,int v)
{
if(!u || !v || u==v) return;
G[u].push_back(v);du[v]++;
};
auto print=[&](int i)
{
int x=b[i].x,y=b[i].y;
if(!b[i].dir) printf("%d %d\n",x+y-1,x+y);
else printf("%d %d\n",x+y-1,x+y+1);
};
for(int i=1;i<=W;i++)
for(int j=1;j<=H;j++)
if(a[i][j]>0) add(bel[i-1][j],bel[i][j]),add(bel[i][j+1],bel[i][j]);
else add(bel[i][j],bel[i-1][j]),add(bel[i][j],bel[i][j+1]);
queue<int> que;
for(int i=1;i<=cnt;i++)
if(!du[i]) que.push(i);
cout<<cnt<<endl;
while(!que.empty())
{
int u=que.front();que.pop();
print(u);
for(int v:G[u])
if(!(--du[v])) que.push(v);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 16376kb
input:
5 2 11221 21112
output:
2 1 3 4 5
result:
ok good job!
Test #2:
score: 0
Accepted
time: 2ms
memory: 17548kb
input:
7 0 2212121 1212122
output:
4 6 7 4 6 2 4 1 2
result:
ok good job!
Test #3:
score: 0
Accepted
time: 1ms
memory: 18000kb
input:
7 2 2212121 1212122
output:
3 1 3 3 5 5 7
result:
ok good job!
Test #4:
score: 0
Accepted
time: 2ms
memory: 15852kb
input:
1 0 1 1
output:
0
result:
ok good job!
Test #5:
score: 0
Accepted
time: 1ms
memory: 16308kb
input:
1 100 2 2
output:
0
result:
ok good job!
Test #6:
score: 0
Accepted
time: 2ms
memory: 17676kb
input:
2 55 12 21
output:
1 1 2
result:
ok good job!
Test #7:
score: 0
Accepted
time: 0ms
memory: 17564kb
input:
3 100 112 211
output:
1 1 3
result:
ok good job!
Test #8:
score: 0
Accepted
time: 0ms
memory: 17456kb
input:
3 99 221 212
output:
1 2 3
result:
ok good job!
Test #9:
score: 0
Accepted
time: 2ms
memory: 15624kb
input:
3 98 111 111
output:
0
result:
ok good job!
Test #10:
score: -100
Wrong Answer
time: 2ms
memory: 16904kb
input:
123 64 222111221111221122211121221221122122211222211112221221212121211221122212111212211222122212122221212121222121221112111112112 211112121222212221122212212122111121121212211211211212212211111221222212121121212222112212222211221211122212111211221122212
output:
128 8 10 12 14 15 17 21 23 30 32 42 44 72 74 76 78 84 86 88 90 110 112 114 116 3 4 37 38 53 54 55 56 57 58 59 60 61 62 65 66 79 80 95 96 97 98 99 100 101 102 105 106 107 108 7 8 9 11 16 18 20 22 23 25 31 33 41 42 44 46 70 72 74 76 82 84 87 88 109 111 112 114 116 118 4 6 52 54 54 56 66 68 78 80 94 96...
result:
wrong answer invalid plan.