QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#50586#3040. ContainertricyzhkxWA 2ms18000kbC++144.3kb2022-09-27 16:10:492022-09-27 16:10:52

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-27 16:10:52]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 18000kb
Show
  • [2022-09-27 16:10:49]
  • Submitted

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;
}
源文件, 语言: C++14

詳細信息

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.
English 繁體中文 简体中文

伺服器時間: 2025-02-08 14:09:09 | 開源專案