QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#393736#6615. Cross the Mazetz3528WA 3ms16084kbC++203.2kb2024-04-19 10:31:422024-04-19 10:31:43

Judging History

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

  • [2024-04-19 10:31:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:16084kb
  • [2024-04-19 10:31:42]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int p_max=110,q_max=1000100;
int n,a,b,s,t,edge=1,l,r;
int d[q_max],now[q_max],to[q_max],Next[q_max],fir[q_max];
int v[q_max],ans=0;
int x[p_max][2],y[p_max][2],h[p_max];
void add(int x,int y,int w){
	to[++edge]=y; v[edge]=w; Next[edge]=fir[x]; fir[x]=edge;
	to[++edge]=x; v[edge]=0; Next[edge]=fir[y]; fir[y]=edge;
}
bool bfs(){
	for(int i=1;i<=t;i++) d[i]=0;
	queue<int> q;
	q.push(s);
	d[s]=1;
	now[s]=fir[s];
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=Next[i]){
			if(!d[to[i]]&&v[i]){//为分层且有权值的边才进行遍历
				q.push(to[i]);
				now[to[i]]=fir[to[i]];
				d[to[i]]=d[x]+1;
				if(to[i]==t) return true;
			}
		}
	}
	return false;
}
int dfs(int u,int flow){
	if(u==t) return flow;
	int rest=flow,k,i;
	for(i=now[u];i&&rest;i=Next[i]){
		if(v[i]&&d[to[i]]==d[u]+1){
			k=dfs(to[i],min(rest,v[i]));//找最小流
			if(!k) d[to[i]]=0;//剪枝,删掉已经增广过的点
			v[i]-=k;
			v[i^1]+=k;
			rest-=k;//从u出发的点要消耗k
		}
	}
	now[u]=i;//将u的下一个结点置空,避免重复
	return flow-rest;//返回在u点的最大流出
}
int dinic(){
	ans=0;
	while(bfs()) ans+=dfs(s,1e9);
	return ans;
}
int num(int k,int x,int y,int flag){return k*a*b+(x-1)*b+y+flag*(a+b+1)*a*b;}
bool check(int mid){
	for(int i=0;i<=t;i++) fir[i]=0;
	edge=1;
	for(int i=1;i<=n;i++) add(s,num(0,x[i][0],y[i][0],0),1);
	for(int i=1;i<=a;i++){
		for(int j=1;j<=b;j++){
			for(int k=0;k<mid;k++){
				add(num(k,i,j,0),num(k,i,j,1),1);
				add(num(k,i,j,1),num(k+1,i,j,0),1);
				if(i>1) add(num(k,i,j,1),num(k+1,i-1,j,0),1);
				if(j>1) add(num(k,i,j,1),num(k+1,i,j-1,0),1);
				if(i<a) add(num(k,i,j,1),num(k+1,i+1,j,0),1);
				if(j<b) add(num(k,i,j,1),num(k+1,i,j+1,0),1);
			}
			add(num(mid,i,j,0),num(mid,i,j,1),1);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=mid;j++){
			add(num(j,x[i][1],y[i][1],1),num(mid,a,b,1)+i,1);
		}
		add(num(mid,a,b,1)+i,t,1);
	}
	return dinic()==n;
}
vector<char> c;
void dfs1(int x,int y,int k){
//	cout<<x<<' '<<y<<endl;
	int u=num(k,x,y,1);
	if(u>num(l,a,b,1)) return ;
	for(int i=fir[u];i;i=Next[i]){
		if(v[i]) continue;
		if(to[i]==num(k+1,x,y,0)) {c.push_back('P');dfs1(x,y,k+1);}
		if(x<a&&to[i]==num(k+1,x+1,y,0)) {c.push_back('D');dfs1(x+1,y,k+1);}
		if(y<b&&to[i]==num(k+1,x,y+1,0)) {c.push_back('R');dfs1(x,y+1,k+1);}
		if(x>1&&to[i]==num(k+1,x-1,y,0)) {c.push_back('U');dfs1(x-1,y,k+1);}
		if(y>1&&to[i]==num(k+1,x,y-1,0)) {c.push_back('L');dfs1(x,y-1,k+1);}
	}
}
int main(){
	cin>>n>>a>>b;
	s=0;t=num(a+b,a,b,1)+n+1;
	l=0,r=a+b;
	for(int i=1;i<=n;i++) cin>>x[i][0]>>y[i][0];
	for(int i=1;i<=n;i++) cin>>x[i][1]>>y[i][1];
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)) r=mid-1;
		else l=mid+1;
	}
	cout<<l<<endl;
	check(l);
	int u=num(0,x[1][0],y[1][0],0);
	for(int i=1;i<=n;i++){
		int j=0;
		c.clear();
		dfs1(x[i][0],y[i][0],0);
		cout<<x[i][0]<<' '<<y[i][0]<<' ';
		for(auto it:c){
			if(it=='U') x[i][0]--;
			if(it=='D') x[i][0]++;
			if(it=='L') y[i][0]--;
			if(it=='R') y[i][0]++;
		}
		cout<<x[i][0]<<' '<<y[i][0]<<' ';
		for(auto it:c) cout<<it,j++;
		while(j<l) cout<<'P',j++;
		cout<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 13832kb

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: 0ms
memory: 13888kb

input:

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

output:

1
1 1 1 1 P
1 2 2 2 D
2 2 2 1 L

result:

ok answer 1

Test #3:

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

input:

2 3 3
1 1
1 3
1 2
2 2

output:

2
1 1 2 2 DR
1 3 1 2 LP

result:

ok answer 2

Test #4:

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

input:

2 10 10
2 9
3 8
10 5
10 10

output:

10
2 9 10 10 DRDDDDDDDP
3 8 10 5 DDDDDDDLLL

result:

ok answer 10

Test #5:

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

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 UPPPP
3 6 2 9 RRRUP
10 1 5 1 UUUUU
10 10 5 10 UUUUU
4 1 6 3 DRRDP

result:

ok answer 5

Test #6:

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

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 4 1 UPPP
6 8 5 8 UPPP
6 3 7 3 DPPP
6 4 8 6 RRDD
3 10 3 8 LLPP
9 5 9 4 LPPP
6 7 7 6 DLPP
4 1 1 2 RUUU

result:

ok answer 4

Test #7:

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

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: 2ms
memory: 14088kb

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: 3ms
memory: 13840kb

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 2 10 RRUUUUU
4 6 3 10 RRRRUPP
10 9 10 2 LLLLLLL
4 7 3 8 RUPPPPP
4 3 3 7 RDRRRUU
10 6 6 4 LLUUUUP
3 3 6 1 DDDLLPP
2 7 1 9 DURRUPP

result:

ok answer 7

Test #10:

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

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: 0ms
memory: 13828kb

input:

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

output:

5
7 8 7 10 RRPPP
4 4 6 7 RRRDD
3 1 2 4 RRRUP

result:

ok answer 5

Test #12:

score: 0
Accepted
time: 3ms
memory: 13908kb

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 LULUU
1 7 2 8 RDPPP
2 1 1 1 RLUPP
5 6 5 3 LLLPP
10 8 7 8 UUUPP
3 5 2 2 LLLUP
9 9 6 9 UUUPP
9 2 9 4 RRPPP
4 9 4 8 LPPPP

result:

ok answer 5

Test #13:

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

input:

2 10 10
9 8
3 3
5 8
4 9

output:

7
9 8 5 8 UUUUPPP
3 3 4 9 RRRRRRD

result:

ok answer 7

Test #14:

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

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 PPPP
8 4 10 4 DDPP
2 8 5 9 RDDD
2 4 4 2 DDLL
10 8 8 10 RRUU
6 6 8 6 DDPP
1 7 3 9 RRDD
10 1 10 2 RPPP

result:

ok answer 4

Test #15:

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

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: 2ms
memory: 13900kb

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 4 10 UPPPPP
3 8 8 9 RDDDDD
2 8 3 6 DLLPPP
3 5 6 5 RDLDDP
4 2 10 2 DDDDDD
8 2 10 6 DDRRRR
7 9 9 6 DDLLLP
3 4 5 5 RDDPPP

result:

ok answer 6

Test #17:

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

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: 2ms
memory: 11872kb

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 UUUUP
4 4 3 1 LLLUP
9 10 10 8 DLLPP
5 7 1 6 LUUUU
10 7 5 7 UUUUU
4 1 4 2 RPPPP
1 5 1 9 RRRRP
6 7 2 6 ULUUU
6 4 8 3 DDLPP
5 3 5 1 LLPPP

result:

ok answer 5

Test #19:

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

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 5 1 DLLLLP
1 5 2 7 RRDPPP
6 5 6 3 LLPPPP
9 6 10 6 DPPPPP
5 5 6 2 DLLLPP
9 3 8 1 LLUPPP
1 10 7 10 DDDDDD

result:

ok answer 6

Test #20:

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

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 4 10 RRRUUUUU
4 1 4 1 PPPPPPPP
9 1 3 1 UUUUUUPP
7 9 2 10 RUUUUUPP
2 6 1 7 RUPPPPPP
9 5 5 1 LLLLUUUU

result:

ok answer 8

Test #21:

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

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 7 8 RPPPP
8 6 8 7 RPPPP
10 3 10 2 LPPPP
6 2 6 1 LPPPP
10 8 8 10 RRUUP
1 10 3 9 DDLPP
9 5 6 4 LUUUP
1 2 3 5 RDDRR
8 3 4 3 UUUUP
10 9 8 9 UUPPP

result:

ok answer 5

Test #22:

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

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 2 9 PPPPPPPP
1 2 7 3 RDDDDDDP
3 9 1 10 RUUPPPPP
6 9 6 10 RPPPPPPP
3 3 9 1 DLDDDDDL
9 2 10 2 DPPPPPPP
2 4 2 5 RPPPPPPP
5 8 5 8 PPPPPPPP
1 6 3 6 DDPPPPPP
4 9 4 2 LLLLLLLP

result:

ok answer 8

Test #23:

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

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 9 7 RUPP
9 2 9 1 LPPP
7 7 7 7 PPPP
7 3 5 1 LLUU
6 8 9 9 DRDD
5 4 3 2 LLUU
2 10 4 8 DDLL
1 1 3 1 DDPP
5 9 6 10 RDPP
4 6 7 6 DDDP

result:

ok answer 4

Test #24:

score: 0
Accepted
time: 3ms
memory: 12044kb

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 17 PPPPPPPPPPPPP
1 49 1 47 LLPPPPPPPPPPP
1 12 1 24 RRRRRRRRRRRRP
1 37 1 28 LLLLLLLLLPPPP
1 83 1 81 LLPPPPPPPPPPP
1 44 1 55 RRRRRRRRRRRPP
1 75 1 75 PPPPPPPPPPPPP
1 78 1 68 LLLLLLLLLLPPP
1 72 1 59 LLLLLLLLLLLLL
1 3 1 6 RRRPPPPPPPPPP

result:

ok answer 13

Test #25:

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

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 RRRRRRRRRRRRRRRRRRRRRRRPP
1 75 1 74 LPPPPPPPPPPPPPPPPPPPPPPPP
1 59 1 68 LRRRRRRRRRRPPPPPPPPPPPPPP
1 42 1 67 RRRRRRRRRRRRRRRRRRRRRRRRR
1 26 1 28 RRPPPPPPPPPPPPPPPPPPPPPPP
1 33 1 58 RRRRRRRRRRRRRRRRRRRRRRRRR
1 88 1 86 LLPPPPPPPPPPPPPPPPPPPPPPP
1 7 1 31 RRRRRRRRRRRRRRRRRRRRRRRRP
1 24 1 39 ...

result:

ok answer 25

Test #26:

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

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 82 LLLLLLPPPPPPPPPPPPPPPPP
1 38 1 15 LLLLLLLLLLLLLLLLLLLLLLL
1 43 1 57 RRRRRRRRRRRRRRPPPPPPPPP
1 99 1 97 LLPPPPPPPPPPPPPPPPPPPPP
1 63 1 74 LLLLLLRRRRRRRRRRRRRRRRR
1 24 1 6 LLLLLLLLLLLLLLLLLLPPPPP
1 44 1 51 RRRRRRRPPPPPPPPPPPPPPPP
1 31 1 14 LLLLLLLLLLLLLLLLLPPPPPP
1 47 1 55 RRRRRRRRPPPPPPPP...

result:

ok answer 23

Test #27:

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

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 8 1 DDPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
96 1 77 1 UUUUUUUUUUUUUUUUUUUPPPPPPPPPPPPPPPP
41 1 33 1 UUUUUUUUPPPPPPPPPPPPPPPPPPPPPPPPPPP
76 1 41 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
97 1 68 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUPPPPPP
72 1 39 1 UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUPP
94 1 84 1 UUUUUUUUUUPPP...

result:

ok answer 35

Test #28:

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

input:

10 100 1
19 1
23 1
29 1
11 1
44 1
87 1
68 1
56 1
35 1
34 1
34 1
63 1
40 1
90 1
8 1
69 1
81 1
41 1
18 1
82 1

output:

28
19 1 18 1 UPPPPPPPPPPPPPPPPPPPPPPPPPPP
23 1 41 1 DDDDDDDDDDDDDDDDDDPPPPPPPPPP
29 1 40 1 DDDDDDDDDDDPPPPPPPPPPPPPPPPP
11 1 8 1 UUUPPPPPPPPPPPPPPPPPPPPPPPPP
44 1 69 1 UDDDDDDDDDDDDDDDDDDDDDDDDDDP
87 1 90 1 DDDPPPPPPPPPPPPPPPPPPPPPPPPP
68 1 82 1 DDDDDDDDDDDDDDPPPPPPPPPPPPPP
56 1 81 1 DDDDDDDDDDDDDDD...

result:

ok answer 28

Test #29:

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

input:

10 100 1
42 1
4 1
64 1
31 1
92 1
45 1
60 1
24 1
8 1
35 1
57 1
70 1
42 1
17 1
72 1
51 1
56 1
87 1
52 1
88 1

output:

34
42 1 72 1 DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDPPPP
4 1 17 1 DDDDDDDDDDDDDPPPPPPPPPPPPPPPPPPPPP
64 1 70 1 DDDDDDPPPPPPPPPPPPPPPPPPPPPPPPPPPP
31 1 56 1 DDDDDDDDDDDDDDDDDDDDDDDDDPPPPPPPPP
92 1 88 1 UUUUPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP
45 1 51 1 DDDDDDPPPPPPPPPPPPPPPPPPPPPPPPPPPP
60 1 87 1 UUUDDDDDDDDDDDDDDD...

result:

ok answer 34

Test #30:

score: 0
Accepted
time: 3ms
memory: 13908kb

input:

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

output:

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

result:

ok answer 5

Test #31:

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

input:

1 1 2
1 1
1 2

output:

1
1 1 1 2 R

result:

ok answer 1

Test #32:

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

input:

1 1 100
1 1
1 100

output:

99
1 1 1 100 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR

result:

ok answer 99

Test #33:

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

input:

2 2 50
1 1
2 50
1 50
2 1

output:

1
1 1 2 1 D
2 50 1 50 U

result:

ok answer 1

Test #34:

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

input:

2 1 100
1 23
1 54
1 67
1 26

output:

13
1 23 1 26 RRRPPPPPPPPPP
1 54 1 67 RRRRRRRRRRRRR

result:

ok answer 13

Test #35:

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

input:

2 2 50
1 21
1 41
2 36
1 11

output:

10
1 21 1 11 LLLLLLLLLL
1 41 2 36 DLLLLLPPPP

result:

ok answer 10

Test #36:

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

input:

2 3 33
3 17
2 13
1 23
1 24

output:

11
3 17 1 24 RRRRRRUURPP
2 13 1 23 RRRRRRRRRRU

result:

ok answer 11

Test #37:

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

input:

2 4 25
3 15
2 22
1 22
1 11

output:

6
3 15 1 11 LLLLUU
2 22 1 22 UPPPPP

result:

ok answer 6

Test #38:

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

input:

2 5 20
2 18
5 2
5 7
3 8

output:

11
2 18 3 8 DLLLLLLLLLL
5 2 5 7 RRRRRPPPPPP

result:

ok answer 11

Test #39:

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

input:

2 6 16
5 12
6 4
1 11
5 15

output:

12
5 12 5 15 RRRPPPPPPPPP
6 4 1 11 RRRRRRRUUUUU

result:

ok answer 12

Test #40:

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

input:

2 7 14
3 14
7 1
1 12
6 4

output:

4
3 14 1 12 LLUU
7 1 6 4 RRRU

result:

ok answer 4

Test #41:

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

input:

2 8 12
8 4
1 4
5 12
2 6

output:

11
8 4 5 12 RRRRRRRRUUU
1 4 2 6 RRDPPPPPPPP

result:

ok answer 11

Test #42:

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

input:

2 9 11
1 7
3 4
4 3
7 6

output:

7
1 7 7 6 DDDDDDL
3 4 4 3 DLPPPPP

result:

ok answer 7

Test #43:

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

input:

2 10 10
4 5
10 7
4 2
2 10

output:

11
4 5 4 2 LLLPPPPPPPP
10 7 2 10 RRRUUUUUUUU

result:

ok answer 11

Test #44:

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

input:

5 100 1
94 1
75 1
91 1
13 1
65 1
76 1
89 1
86 1
92 1
19 1

output:

11
94 1 89 1 UUUUUPPPPPP
75 1 86 1 DDDDDDDDDDD
91 1 92 1 DPPPPPPPPPP
13 1 19 1 DDDDDDPPPPP
65 1 76 1 DDDDDDDDDDD

result:

ok answer 11

Test #45:

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

input:

5 50 2
33 1
12 2
39 1
36 1
19 2
6 1
41 2
32 2
34 2
9 2

output:

10
33 1 34 2 RDPPPPPPPP
12 2 6 1 UUULUUUPPP
39 1 41 2 RDDPPPPPPP
36 1 32 2 RUUUUPPPPP
19 2 9 2 UUUUUUUUUU

result:

ok answer 10

Test #46:

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

input:

5 33 3
33 3
4 1
23 1
23 3
27 1
32 2
4 1
20 2
21 3
28 1

output:

4
33 3 32 2 LUPP
4 1 4 1 PPPP
23 1 20 2 RUUU
23 3 21 3 UUPP
27 1 28 1 DPPP

result:

ok answer 4

Test #47:

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

input:

5 25 4
23 3
22 3
9 4
18 3
1 3
23 4
9 2
7 3
19 3
13 2

output:

6
23 3 23 4 RPPPPP
22 3 19 3 UUUPPP
9 4 9 2 LLPPPP
18 3 13 2 LUUUUU
1 3 7 3 DDDDDD

result:

ok answer 6

Test #48:

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

input:

5 20 5
11 5
15 3
16 5
12 2
15 2
20 2
8 2
19 1
3 2
15 5

output:

9
11 5 8 2 LLLUUUPPP
15 3 19 1 DDDDLLPPP
16 5 15 5 UPPPPPPPP
12 2 3 2 UUUUUUUUU
15 2 20 2 DDDDDPPPP

result:

ok answer 9

Test #49:

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

input:

5 16 6
13 2
5 2
2 6
16 2
3 4
3 4
2 3
14 2
1 4
1 2

output:

12
13 2 3 4 RRUUUUUUUUUU
5 2 1 2 UUUUPPPPPPPP
2 6 2 3 LLLPPPPPPPPP
16 2 14 2 UUPPPPPPPPPP
3 4 1 4 UUPPPPPPPPPP

result:

ok answer 12

Test #50:

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

input:

5 14 7
4 3
1 1
3 3
3 4
13 7
3 3
8 3
12 7
1 5
2 7

output:

4
4 3 8 3 DDDD
1 1 1 5 RRRR
3 3 3 3 PPPP
3 4 2 7 RURR
13 7 12 7 UPPP

result:

ok answer 4

Test #51:

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

input:

5 12 8
12 7
11 8
1 7
4 8
11 4
7 6
5 8
6 3
10 4
2 1

output:

7
12 7 10 4 LLLUUPP
11 8 7 6 LLUUUUP
1 7 2 1 DLLLLLL
4 8 5 8 DPPPPPP
11 4 6 3 ULUUUUP

result:

ok answer 7

Test #52:

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

input:

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

output:

5
3 3 4 5 RRDPP
1 1 1 4 RRRPP
10 6 6 7 RUUUU
1 4 2 6 RRDPP
10 4 7 3 LUUUP

result:

ok answer 5

Test #53:

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

input:

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

output:

7
2 2 2 5 RRRPPPP
1 3 1 10 RRRRRRR
9 9 10 6 DLLLPPP
7 4 9 5 RDDPPPP
6 5 6 5 PPPPPPP

result:

ok answer 7

Test #54:

score: 0
Accepted
time: 3ms
memory: 10252kb

input:

10 1 100
1 67
1 1
1 86
1 24
1 75
1 82
1 55
1 84
1 26
1 40
1 4
1 62
1 73
1 77
1 5
1 14
1 42
1 98
1 48
1 38

output:

19
1 67 1 48 LLLLLLLLLLLLLLLLLLL
1 1 1 4 RRRPPPPPPPPPPPPPPPP
1 86 1 98 RRRRRRRRRRRRPPPPPPP
1 24 1 5 LLLLLLLLLLLLLLLLLLL
1 75 1 62 RRLLLLLLLLLLLLLLLPP
1 82 1 73 LLLLLLLLLPPPPPPPPPP
1 55 1 42 LLLLLLLLLLLLLPPPPPP
1 84 1 77 LLLLLLLPPPPPPPPPPPP
1 26 1 14 RRRLLLLLLLLLLLLLLLP
1 40 1 38 RRLLLLLLLRRRPPPPPPP

result:

ok answer 19

Test #55:

score: -100
Wrong Answer
time: 0ms
memory: 11824kb

input:

10 2 50
2 47
1 48
1 33
1 22
1 10
2 5
1 49
1 11
2 11
1 47
2 48
2 42
1 48
2 17
1 23
1 12
2 23
1 6
2 29
1 32

output:

15
2 47 2 42 PLLLLLPPPPPPPPP
1 48 2 48 DPPPPPPPPPPPPPP
1 33 2 29 LDLLLPPPPPPPPPP
1 22 1 23 RPPPPPPPPPPPPPP
1 10 2 23 RRRRRRRRRRRRRDP
2 5 1 6 RUPPPPPPPPPPPPP
1 49 1 48 LPPPPPPPPPPPPPP
1 11 1 12 RPPPPPPPPPPPPPP
2 11 2 17 RRRRRRPPPPPPPPP
1 47 1 32 LLLLLLLLLLLLLLL

result:

wrong answer back to maze