QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164254#6615. Cross the MazeLFCodeWA 4ms5956kbC++143.7kb2023-09-04 20:57:102023-09-04 20:57:10

Judging History

你现在查看的是最新测评结果

  • [2023-09-04 20:57:10]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:5956kb
  • [2023-09-04 20:57:10]
  • 提交

answer

#include<cstdio>
#include<cstdlib>
#define lg(x) (31-__builtin_clz(x))
#define llg(x) (63-__builtin_clzll(x))
const int N=114,P=100086,MOD=998244353,INF=1e9+7;
int n,a,b,qh,qt,s,t,tot,ax,ay;
int px[N],py[N],qx[N],qy[N],d[P],h[P],fir[P],q[P];
int xx[4]={-1,0,1,0},
    yy[4]={0,-1,0,1};
char ansl[N*3];
struct edge{int v,w,nxt;}e[5000086];
int Abs(int x){return x<0?-x:x;}
int lowbit(int x){return x&(-x);}
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int Swap(int &a,int &b){a^=b^=a^=b;return true;}
int Add(int &a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int vAdd(int a,int b){return(a+=b)>=MOD?a-=MOD:a;}
int Sub(int &a,int b){return(a-=b)<0?a+=MOD:a;}
int vSub(int a,int b){return(a-=b)<0?a+=MOD:a;}
int Mul(int a,int b){return 1ll*a*b%MOD;}
int qpow(int a,int b){
	int ret=1;
	while(b){if(b&1)ret=Mul(ret,a);a=Mul(a,a);b>>=1;}
	return ret;
}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool add(int u,int v,int w){e[++tot].v=v;e[tot].w=w;e[tot].nxt=h[u];h[u]=tot;return true;}
bool otm(int x,int y){return x<1||x>a||y<1||y>b;}
int pos(int x,int y,int t,int flr){return (t*a*b+b*(x-1)+y)*2-flr;}
bool bfs(){
	for(int i=0;i<=t;i++)fir[i]=d[i]=0;
	d[q[qh=qt=1]=s]=1;fir[s]=h[s];
	while(qh<=qt){
		int np=q[qh++];
		for(int i=h[np];i;i=e[i].nxt){
			if(e[i].w==0||d[e[i].v])continue;
			d[e[i].v]=d[np]+1;
			fir[e[i].v]=h[e[i].v];
			q[++qt]=e[i].v;
			if(e[i].v==t){
				while(0);
				return true;
			}
		}
	}
	return false;
}
int dfs(int np,int flw){
	if(np==t)return flw;int rst=flw;
	for(int i=fir[np];i&&rst;i=e[i].nxt){
		fir[np]=i;
		if(e[i].w==0||d[e[i].v]!=d[np]+1)continue;
		int k=dfs(e[i].v,Min(rst,e[i].w));
		if(!k)d[e[i].v]=0;
		e[i].w-=k;e[i^1].w+=k;rst-=k;
	}
	return flw-rst;
}
int dinic(){
	int delta=0,ans=0;
	while(bfs())while(delta=dfs(s,INF))ans+=delta;
	return ans;
}
bool solve(int tme){
	s=0;t=(tme+1)*a*b*2+1;tot=1;
	for(int i=s;i<=t;i++)h[i]=0;
	for(int i=0;i<=tme;i++)
		for(int x=1;x<=a;x++)
			for(int y=1;y<=b;y++){
				add(pos(x,y,i,1),pos(x,y,i,0),1);
				add(pos(x,y,i,0),pos(x,y,i,1),0);
				if(i==tme)continue;
				add(pos(x,y,i,0),pos(x,y,i+1,1),1);
				add(pos(x,y,i+1,1),pos(x,y,i,0),0);
				for(int j=0;j<4;j++){
					if(otm(x+xx[j],y+yy[j]))continue;
					add(pos(x,y,i,0),pos(x+xx[j],y+yy[j],i+1,1),1);
					add(pos(x+xx[j],y+yy[j],i+1,1),pos(x,y,i,0),0);
				}
			}
	for(int i=1;i<=n;i++){
		add(0,pos(px[i],py[i],0,1),1);
		add(pos(px[i],py[i],0,1),0,0);
		add(pos(qx[i],qy[i],tme,0),t,1);
		add(t,pos(qx[i],qy[i],tme,0),0);
	}
	return dinic()==n;
}
bool getans(int x,int y,int t,int lim){
	if(t==lim){ax=x;ay=y;return true;}int np=pos(x,y,t,0);
	for(int i=h[np];i;i=e[i].nxt){
		if(e[i].w)continue;
		if(e[i].v==pos(x,y,t+1,1)){ansl[t]='S';return getans(x,y,t+1,lim);}
		if(e[i].v==pos(x,y-1,t+1,1)){ansl[t]='L';return getans(x,y-1,t+1,lim);}
		if(e[i].v==pos(x,y+1,t+1,1)){ansl[t]='R';return getans(x,y+1,t+1,lim);}
		if(e[i].v==pos(x-1,y,t+1,1)){ansl[t]='U';return getans(x-1,y,t+1,lim);}
		if(e[i].v==pos(x+1,y,t+1,1)){ansl[t]='D';return getans(x+1,y,t+1,lim);}
	}
	return false;
}
bool print(int x,int ans){
	getans(px[x],py[x],0,ans);
	printf("%d %d %d %d ",px[x],py[x],ax,ay);
	for(int i=0;i<ans;i++)putchar(ansl[i]);
	putchar('\n');
	return true;
}
int main(){
	n=read();a=read();b=read();
	for(int i=1;i<=n;i++){px[i]=read();py[i]=read();}
	for(int i=1;i<=n;i++){qx[i]=read();qy[i]=read();}
	int mx=a+b+n,np=0;
	for(int i=lg(mx);i+1;i--){
		if(np+(1<<i)>mx)continue;
		if(!solve(np+(1<<i)))np+=(1<<i);
	}
	solve(++np);printf("%d\n",np);
	for(int i=1;i<=n;i++)print(i,np);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 1548kb

input:

3 4 4
1 1
1 4
4 4
1 3
2 3
2 4

output:

2
1 1 1 3 RR
1 4 2 3 DL
4 4 2 4 UU

result:

ok answer 2

Test #2:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

3 2 2
1 1
1 2
2 2
1 1
2 1
2 2

output:

1
1 1 1 1 S
1 2 2 2 D
2 2 2 1 L

result:

ok answer 1

Test #3:

score: 0
Accepted
time: 1ms
memory: 3560kb

input:

2 3 3
1 1
1 3
1 2
2 2

output:

2
1 1 1 2 RS
1 3 2 2 DL

result:

ok answer 2

Test #4:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

2 10 10
2 9
3 8
10 5
10 10

output:

10
2 9 10 10 DRDDDDDDDS
3 8 10 5 DDDDDDDLLL

result:

ok answer 10

Test #5:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

6 10 10
4 9
4 2
3 6
10 1
10 10
4 1
6 8
5 10
6 3
5 1
2 9
3 2

output:

5
4 9 6 8 RDDLL
4 2 3 2 RRLLU
3 6 2 9 RRRUS
10 1 5 1 UUUUU
10 10 5 10 UUUUU
4 1 6 3 RRDDS

result:

ok answer 5

Test #6:

score: 0
Accepted
time: 1ms
memory: 3776kb

input:

8 10 10
5 1
6 8
6 3
6 4
3 10
9 5
6 7
4 1
3 8
7 3
1 2
8 6
5 8
7 6
9 4
4 1

output:

4
5 1 7 3 RRDD
6 8 7 6 LLDS
6 3 4 1 UULL
6 4 9 4 SDDD
3 10 3 8 DLLU
9 5 8 6 RRLU
6 7 5 8 RRLU
4 1 1 2 RUUU

result:

ok answer 4

Test #7:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

1 10 10
8 3
8 4

output:

1
8 3 8 4 R

result:

ok answer 1

Test #8:

score: 0
Accepted
time: 0ms
memory: 5808kb

input:

1 10 10
10 1
6 6

output:

9
10 1 6 6 RRRRRUUUU

result:

ok answer 9

Test #9:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

8 10 10
7 8
4 6
10 9
4 7
4 3
10 6
3 3
2 7
3 7
2 10
3 8
1 9
6 1
3 10
10 2
6 4

output:

7
7 8 3 7 RLLUUUU
4 6 1 9 RRRUUUS
10 9 10 2 LLLLLLL
4 7 3 8 RRRLULS
4 3 6 1 RDDLLLS
10 6 6 4 UUUSLLU
3 3 3 10 RRRRRRR
2 7 2 10 RRRDDUU

result:

ok answer 7

Test #10:

score: 0
Accepted
time: 0ms
memory: 1756kb

input:

1 10 10
10 3
2 6

output:

11
10 3 2 6 RRRUUUUUUUU

result:

ok answer 11

Test #11:

score: 0
Accepted
time: 1ms
memory: 3824kb

input:

3 10 10
7 8
4 4
3 1
7 10
6 7
2 4

output:

5
7 8 7 10 RRDUS
4 4 6 7 RRRDD
3 1 2 4 RRRUS

result:

ok answer 5

Test #12:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

9 10 10
6 4
1 7
2 1
5 6
10 8
3 5
9 9
9 2
4 9
5 3
3 2
6 9
2 2
9 4
7 8
2 8
1 1
4 8

output:

5
6 4 3 2 UUULL
1 7 4 8 DDRDS
2 1 1 1 RRLLU
5 6 2 8 RRUUU
10 8 9 4 LLLLU
3 5 2 2 LUSLL
9 9 7 8 RLLUU
9 2 5 3 RUUUU
4 9 6 9 RDDLS

result:

ok answer 5

Test #13:

score: 0
Accepted
time: 1ms
memory: 5756kb

input:

2 10 10
9 8
3 3
5 8
4 9

output:

7
9 8 5 8 RLUUUUS
3 3 4 9 RRRRRRD

result:

ok answer 7

Test #14:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

8 10 10
10 5
8 4
2 8
2 4
10 8
6 6
1 7
10 1
8 6
10 5
10 2
5 9
8 10
10 4
3 9
4 2

output:

4
10 5 10 5 RLLR
8 4 10 4 RDDL
2 8 5 9 RDDD
2 4 4 2 DDLL
10 8 8 10 RRUU
6 6 8 6 RDDL
1 7 3 9 RRDD
10 1 10 2 RRLS

result:

ok answer 4

Test #15:

score: 0
Accepted
time: 1ms
memory: 3796kb

input:

1 10 10
1 9
2 10

output:

2
1 9 2 10 RD

result:

ok answer 2

Test #16:

score: 0
Accepted
time: 1ms
memory: 3792kb

input:

8 10 10
5 10
3 8
2 8
3 5
4 2
8 2
7 9
3 4
8 9
9 6
3 6
10 2
4 10
10 6
6 5
5 5

output:

6
5 10 8 9 DDDLSS
3 8 6 5 DDDLLL
2 8 4 10 DLRRRD
3 5 5 5 RDLRDL
4 2 10 2 DDDDDD
8 2 10 6 RRRRDD
7 9 9 6 DDLLSL
3 4 3 6 RRRRLL

result:

ok answer 6

Test #17:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

1 10 10
8 6
1 8

output:

9
8 6 1 8 RRUUUUUUU

result:

ok answer 9

Test #18:

score: 0
Accepted
time: 0ms
memory: 1876kb

input:

10 10 10
7 10
4 4
9 10
5 7
10 7
4 1
1 5
6 7
6 4
5 3
5 7
1 9
1 6
8 3
5 1
10 8
2 6
4 2
3 10
3 1

output:

5
7 10 3 10 UUSUU
4 4 4 2 RLSLL
9 10 10 8 LLUDD
5 7 1 6 LUUUU
10 7 5 7 UUUUU
4 1 3 1 RRLLU
1 5 1 9 RRRRS
6 7 2 6 LUUUU
6 4 8 3 RDDLL
5 3 5 1 RLLLS

result:

ok answer 5

Test #19:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

7 10 10
4 5
1 5
6 5
9 6
5 5
9 3
1 10
10 6
6 2
5 1
2 7
8 1
7 10
6 3

output:

6
4 5 6 2 DDLLLS
1 5 2 7 RRDDUS
6 5 6 3 RRLLLL
9 6 8 1 LLLLLU
5 5 5 1 RLLLLL
9 3 10 6 RRRRDL
1 10 7 10 DDDDDD

result:

ok answer 6

Test #20:

score: 0
Accepted
time: 1ms
memory: 3780kb

input:

6 10 10
9 7
4 1
9 1
7 9
2 6
9 5
5 1
4 1
2 10
4 10
3 1
1 7

output:

8
9 7 1 7 UUUUUUUU
4 1 4 1 RRRRLLLL
9 1 3 1 RLUUUUUU
7 9 2 10 RLUUUURU
2 6 4 10 RRRRDDDU
9 5 5 1 LLLLUUUU

result:

ok answer 8

Test #21:

score: 0
Accepted
time: 1ms
memory: 3788kb

input:

10 10 10
7 7
8 6
10 3
6 2
10 8
1 10
9 5
1 2
8 3
10 9
8 9
8 10
6 4
7 8
4 3
3 5
3 9
6 1
8 7
10 2

output:

5
7 7 6 4 LLULS
8 6 8 7 LSRRS
10 3 10 2 RRLLL
6 2 6 1 RRLLL
10 8 7 8 RUULU
1 10 3 9 DDDLU
9 5 8 9 RRRRU
1 2 3 5 RRRDD
8 3 4 3 UUUUS
10 9 8 10 RLRUU

result:

ok answer 5

Test #22:

score: 0
Accepted
time: 1ms
memory: 3748kb

input:

10 10 10
2 9
1 2
3 9
6 9
3 3
9 2
2 4
5 8
1 6
4 9
1 10
6 10
3 6
2 5
4 2
7 3
10 2
9 1
2 9
5 8

output:

8
2 9 1 10 LLSRRRUS
1 2 4 2 RRDDDLLS
3 9 2 5 RLLSLLLU
6 9 7 3 DLLLLLLS
3 3 9 1 DDDDDDLL
9 2 10 2 RRRDLLLS
2 4 3 6 RRDRRLLS
5 8 5 8 RDDDLUUU
1 6 2 9 RRRRDDLU
4 9 6 10 RDDDDUUS

result:

ok answer 8

Test #23:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

10 10 10
10 6
9 2
7 7
7 3
6 8
5 4
2 10
1 1
5 9
4 6
5 1
9 9
9 1
7 6
3 2
4 8
7 7
9 7
3 1
6 10

output:

4
10 6 7 7 UUUR
9 2 9 1 RLLS
7 7 9 7 RDDL
7 3 5 1 LLUU
6 8 9 9 RDDD
5 4 3 2 LLUU
2 10 4 8 DDLL
1 1 3 1 RDDL
5 9 6 10 RDDU
4 6 7 6 DSDD

result:

ok answer 4

Test #24:

score: 0
Accepted
time: 0ms
memory: 2300kb

input:

10 1 100
1 17
1 49
1 12
1 37
1 83
1 44
1 75
1 78
1 72
1 3
1 75
1 47
1 55
1 81
1 6
1 59
1 17
1 68
1 28
1 24

output:

13
1 17 1 24 RRRRRRRRRRLLL
1 49 1 47 RRRRRLLLLLLLS
1 12 1 17 RRRRRRRRRLLLL
1 37 1 28 RRLLLLLLLLLLL
1 83 1 75 LLSRLLSLLLLLS
1 44 1 55 RRRRRRRRRRRRL
1 75 1 68 RRRLLLLLLLLLL
1 78 1 81 RRLLLRRRRRRLL
1 72 1 59 LLLLLLLLLLLLL
1 3 1 6 RRRRRRRRLLLLL

result:

ok answer 13

Test #25:

score: 0
Accepted
time: 1ms
memory: 2296kb

input:

10 1 100
1 43
1 75
1 59
1 42
1 26
1 33
1 88
1 7
1 24
1 95
1 68
1 31
1 39
1 74
1 66
1 67
1 28
1 70
1 86
1 58

output:

25
1 43 1 66 RRRRRRRRRRRRRRRRRRRRRRRRL
1 75 1 68 RRRRRRRRLLLLLLLSLLLLLLLLS
1 59 1 70 RRRRRRRRRRRRRRRRRRLLLLLLL
1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR
1 26 1 28 RRRRRRRRRRRRSLLLLLLLLSLLS
1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR
1 88 1 74 RRRRRLLLLLLLLLLLLLLLLLLLS
1 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRS
1 24 1 39 ...

result:

ok answer 25

Test #26:

score: 0
Accepted
time: 2ms
memory: 2344kb

input:

10 1 100
1 88
1 38
1 43
1 99
1 63
1 24
1 44
1 31
1 47
1 52
1 6
1 14
1 55
1 15
1 82
1 57
1 73
1 74
1 97
1 51

output:

23
1 88 1 74 RRRRLLLLLLLLLLLLLLLLLSL
1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL
1 43 1 51 LLLLLLRRRRRRRRRRRRRRRLS
1 99 1 97 RLRLRLRLRLRLRLRLRLRLLLS
1 63 1 82 RRRRRRRRRRRRRRRRRRRRRLL
1 24 1 6 RRLLLLLLLLLLLLLLLLLLLLS
1 44 1 55 RRRRRRRRRRRRRRRRRLLLLLL
1 31 1 14 RRLLLSLLLLLLLLLLLLLLLLS
1 47 1 57 RRRRRRRRRRRRRRRR...

result:

ok answer 23

Test #27:

score: -100
Wrong Answer
time: 4ms
memory: 5956kb

input:

10 100 1
6 1
96 1
41 1
76 1
97 1
72 1
94 1
82 1
23 1
40 1
31 1
33 1
84 1
77 1
41 1
24 1
39 1
68 1
8 1
82 1

output:

35
6 1 6 26 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLLLL
96 1 96 -11 LLLLLLLRRRRRRRRRRRLLLLLLLLLLLLLLLLS
41 1 41 -16 RRRRRRRRRLLLLLLLLLLLLLLLLLLLLLLLLLL
76 1 76 -34 LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
97 1 97 -14 LSRRRRLRLRLRLRLRSLLLLLLLLLLLLLLLLLL
72 1 72 -32 RLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL
94 1 94 -16 ...

result:

wrong answer Integer parameter [name=ey_0] equals to 26, violates the range [1, 1]