QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76398#3816. Home alone: Johnny lost in New YorkAFewSunsWA 3ms5632kbC++149.8kb2023-02-09 19:46:432023-02-09 19:46:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-09 19:46:44]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5632kb
  • [2023-02-09 19:46:43]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
namespace my_std{
	#define ll long long
	#define bl bool
	ll my_pow(ll a,ll b,ll mod){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res=(res*a)%mod;
			a=(a*a)%mod;
			b>>=1;
		}
		return res;
	}
	ll qpow(ll a,ll b){
		ll res=1;
		if(!b) return 1;
		while(b){
			if(b&1) res*=a;
			a*=a;
			b>>=1;
		}
		return res;
	}
	#define db double
	#define pf printf
	#define pc putchar
	#define fr(i,x,y) for(register ll i=(x);i<=(y);i++)
	#define pfr(i,x,y) for(register ll i=(x);i>=(y);i--)
	#define go(u) for(ll i=head[u];i;i=e[i].nxt)
	#define enter pc('\n')
	#define space pc(' ')
	#define fir first
	#define sec second
	#define MP make_pair
	#define il inline
	#define inf 8e18
	#define random(x) rand()*rand()%(x)
	#define inv(a,mod) my_pow((a),(mod-2),(mod))
	il ll read(){
		ll sum=0,f=1;
		char ch=0;
		while(!isdigit(ch)){
			if(ch=='-') f=-1;
			ch=getchar();
		}
		while(isdigit(ch)){
			sum=sum*10+(ch^48);
			ch=getchar();
		}
		return sum*f;
	}
	il void write(ll x){
		if(x<0){
			x=-x;
			pc('-');
		}
		if(x>9) write(x/10);
		pc(x%10+'0');
	}
	il void writeln(ll x){
		write(x);
		enter;
	}
	il void writesp(ll x){
		write(x);
		space;
	}
}
using namespace my_std;
ll n,m,cnt=0,dir[1010][1010],d[4][2]={{0,-1},{1,0},{0,1},{-1,0}};
bl ck[1010][1010];
bl doleft(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy);
bl doright(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy);
bl doup(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy);
bl dodown(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy);
bl dfs0(ll x,ll y,ll xx,ll yy,ll edx,ll edy,ll nx,ll ny,ll dep){
	ck[nx][ny]=1;
	if(nx==edx&&ny==edy&&dep==(xx-x+1)*(yy-y+1)) return 1;
	if(nx==edx&&ny==edy){
		ck[nx][ny]=0;
		return 0;
	}
	fr(i,0,3){
		ll px=nx+d[i][0],py=ny+d[i][1];
		if(px<x||px>xx||py<y||py>yy) continue;
		dir[nx][ny]=i;
		if(ck[px][py]) continue;
		if(dfs0(x,y,xx,yy,edx,edy,px,py,dep+1)) return 1;
	}
	ck[nx][ny]=0;
	return 0;
}
void dfs1(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	if((xx-x+1)<=5&&(yy-y+1)<=5){
		if(!dfs0(x,y,xx,yy,edx,edy,stx,sty,1)){
			pf("NIE\n");
			exit(0);
		}
		return;
	}
	if((xx-x+1)>5){
		if(doleft(x,y,xx,yy,stx,sty,edx,edy)) return;
		if(doright(x,y,xx,yy,stx,sty,edx,edy)) return;
	}
	if((yy-y+1)>5){
		if(doup(x,y,xx,yy,stx,sty,edx,edy)) return;
		if(dodown(x,y,xx,yy,stx,sty,edx,edy)) return;
	}
}
bl doleft(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	if(stx>=(x+2)){
		dfs1(x+2,y,xx,yy,stx,sty,edx,edy);
		fr(i,y,yy-1){
			if(dir[x+2][i]==2){
				dir[x+2][i]=3;
				fr(j,y+1,i) dir[x+1][j]=0;
				dir[x+1][y]=3;
				fr(j,y,yy-1) dir[x][j]=2;
				dir[x][yy]=1;
				fr(j,i+2,yy) dir[x+1][j]=0;
				dir[x+1][i+1]=1;
				return 1;
			}
		}
		fr(i,y+1,yy){
			if(dir[x+2][i]==0){
				dir[x+2][i]=3;
				fr(j,i,yy-1) dir[x+1][j]=2;
				dir[x+1][yy]=3;
				fr(j,y+1,yy) dir[x][j]=0;
				dir[x][y]=1;
				fr(j,y,i-2) dir[x+1][j]=2;
				dir[x+1][i-1]=1;
				return 1;
			}
		}
	}
	if((x+2)<=edx){
		if(x==stx){
			if(sty<(yy-1)){
				dfs1(x+2,y,xx,yy,stx+2,sty+2,edx,edy);
				fr(i,y+1,sty) dir[x][i]=0;
				dir[x][y]=1;
				fr(i,y,sty) dir[x+1][i]=2;
				dir[x+1][sty+1]=3;
				fr(i,sty+1,yy-1) dir[x][i]=2;
				dir[x][yy]=1;
				fr(i,sty+3,yy) dir[x+1][i]=0;
				dir[x+1][sty+2]=1;
			}
			else{
				dfs1(x+2,y,xx,yy,stx+2,sty-2,edx,edy);
				fr(i,sty,yy-1) dir[x][i]=2;
				dir[x][yy]=1;
				fr(i,sty,yy) dir[x+1][i]=0;
				dir[x+1][sty-1]=3;
				fr(i,y+1,sty-1) dir[x][i]=0;
				dir[x][y]=1;
				fr(i,y,sty-3) dir[x+1][i]=2;
				dir[x+1][sty-2]=1;
			}
		}
		else{
			if(sty<yy){
				dfs1(x+2,y,xx,yy,stx+1,sty+1,edx,edy);
				fr(i,y+1,sty) dir[x+1][i]=0;
				dir[x+1][y]=3;
				fr(i,y,yy-1) dir[x][i]=2;
				dir[x][yy]=1;
				fr(i,sty+2,yy) dir[x+1][i]=0;
				dir[x+1][sty+1]=1;
			}
			else{
				dfs1(x+2,y,xx,yy,stx+1,sty-1,edx,edy);
				fr(i,sty,yy-1) dir[x+1][i]=2;
				dir[x+1][yy]=3;
				fr(i,y+1,yy) dir[x][i]=0;
				dir[x][y]=1;
				fr(i,y,sty-2) dir[x+1][i]=2;
				dir[x+1][sty-1]=1;
			}
		}
		return 1;
	}
	return 0;
}
bl doright(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	if(edx<=(xx-2)){
		dfs1(x,y,xx-2,yy,stx,sty,edx,edy);
		fr(i,y,yy-1){
			if(dir[xx-2][i]==2){
				dir[xx-2][i]=1;
				fr(j,y+1,i) dir[xx-1][j]=0;
				dir[xx-1][y]=1;
				fr(j,y,yy-1) dir[xx][j]=2;
				dir[xx][yy]=3;
				fr(j,i+2,yy) dir[xx-1][j]=0;
				dir[xx-1][i+1]=3;
				return 1;
			}
		}
		fr(i,y+1,yy){
			if(dir[xx-2][i]==0){
				dir[xx-2][i]=1;
				fr(j,i,yy-1) dir[xx-1][j]=2;
				dir[xx-1][yy]=1;
				fr(j,y+1,yy) dir[xx][j]=0;
				dir[xx][y]=3;
				fr(j,y,i-2) dir[xx-1][j]=2;
				dir[xx-1][i-1]=3;
				return 1;
			}
		}
	}
	if((xx-2)>=stx){
		if(xx==edx){
			if(edy<(yy-1)){
				dfs1(x,y,xx-2,yy,stx,sty,edx-2,edy+2);
				fr(i,y+1,edy) dir[xx][i]=0;
				dir[xx][y]=3;
				fr(i,y,edy) dir[xx-1][i]=2;
				dir[xx-1][edy+1]=1;
				fr(i,edy+1,yy-1) dir[xx][i]=2;
				dir[xx][yy]=3;
				fr(i,edy+3,yy) dir[xx-1][i]=0;
				dir[xx-1][edy+2]=3;
			}
			else{
				dfs1(x,y,xx-2,yy,stx,sty,edx-2,edy-2);
				fr(i,edy,yy-1) dir[xx][i]=2;
				dir[xx][yy]=3;
				fr(i,edy,yy) dir[xx-1][i]=0;
				dir[xx-1][edy-1]=1;
				fr(i,y+1,edy-1) dir[xx][i]=0;
				dir[xx][y]=3;
				fr(i,y,edy-3) dir[xx-1][i]=2;
				dir[xx-1][edy-2]=3;
			}
		}
		else{
			if(edy<yy){
				dfs1(x,y,xx-2,yy,stx,sty,edx-1,edy+1);
				fr(i,y+1,edy) dir[xx-1][i]=0;
				dir[xx-1][y]=1;
				fr(i,y,yy-1) dir[xx][i]=2;
				dir[xx][yy]=3;
				fr(i,edy+2,yy) dir[xx-1][i]=0;
				dir[xx-1][edy+1]=3;
			}
			else{
				dfs1(x,y,xx-2,yy,stx,sty,edx-1,edy-1);
				fr(i,edy,yy-1) dir[xx-1][i]=2;
				dir[xx-1][yy]=1;
				fr(i,y+1,yy) dir[xx][i]=0;
				dir[xx][y]=3;
				fr(i,y,edy-2) dir[xx-1][i]=2;
				dir[xx-1][edy-1]=3;
			}
		}
		return 1;
	}
	return 0;
}
bl doup(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	if(sty>=(y+2)){
		dfs1(x,y+2,xx,yy,stx,sty,edx,edy);
		fr(i,x,xx-1){
			if(dir[i][y+2]==1){
				dir[i][y+2]=0;
				fr(j,x+1,i) dir[j][y+1]=3;
				dir[x][y+1]=0;
				fr(j,x,xx-1) dir[j][y]=1;
				dir[xx][y]=2;
				fr(j,i+2,xx) dir[j][y+1]=3;
				dir[i+1][y+1]=2;
				return 1;
			}
		}
		fr(i,x+1,xx){
			if(dir[i][y+2]==3){
				dir[i][y+2]=0;
				fr(j,i,xx-1) dir[j][y+1]=1;
				dir[xx][y+1]=0;
				fr(j,x+1,xx) dir[j][y]=3;
				dir[x][y]=2;
				fr(j,x,i-2) dir[j][y+1]=1;
				dir[i-1][y+1]=2;
				return 1;
			}
		}
	}
	if((y+2)<=edy){
		if(y==sty){
			if(stx<(xx-1)){
				dfs1(x,y+2,xx,yy,stx+2,sty+2,edx,edy);
				fr(i,x+1,stx) dir[i][y]=3;
				dir[x][y]=2;
				fr(i,x,stx) dir[i][y+1]=1;
				dir[stx+1][y+1]=0;
				fr(i,stx+1,xx-1) dir[i][y]=1;
				dir[xx][y]=2;
				fr(i,stx+3,xx) dir[i][y+1]=3;
				dir[stx+2][y+1]=2;
			}
			else{
				dfs1(x,y+2,xx,yy,stx-2,sty+2,edx,edy);
				fr(i,stx,xx-1) dir[i][y]=1;
				dir[xx][y]=2;
				fr(i,stx,xx) dir[i][y+1]=3;
				dir[stx-1][y+1]=0;
				fr(i,x+1,stx-1) dir[i][y]=3;
				dir[x][y]=2;
				fr(i,x,stx-3) dir[i][y+1]=1;
				dir[stx-2][y+1]=2;
			}
		}
		else{
			if(stx<xx){
				dfs1(x,y+2,xx,yy,stx+1,sty+1,edx,edy);
				fr(i,x+1,stx) dir[i][y+1]=3;
				dir[x][y+1]=0;
				fr(i,x,xx-1) dir[i][y]=1;
				dir[xx][y]=2;
				fr(i,stx+2,xx) dir[i][y+1]=3;
				dir[stx+1][y+1]=2;
			}
			else{
				dfs1(x,y+2,xx,yy,stx-1,sty+1,edx,edy);
				fr(i,stx,xx-1) dir[i][y+1]=1;
				dir[xx][y+1]=0;
				fr(i,x+1,xx) dir[i][y]=3;
				dir[x][y]=2;
				fr(i,x,stx-2) dir[i][y+1]=1;
				dir[stx-1][y+1]=2;
			}
		}
		return 1;
	}
	return 0;
}
bl dodown(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	if(edy<=(yy-2)){
		dfs1(x,y,xx,yy-2,stx,sty,edx,edy);
		fr(i,x,xx-1){
			if(dir[i][yy-2]==1){
				dir[i][yy-2]=2;
				fr(j,x+1,i) dir[j][yy-1]=3;
				dir[x][yy-1]=2;
				fr(j,x,xx-1) dir[j][yy]=1;
				dir[xx][yy]=0;
				fr(j,i+2,xx) dir[j][yy-1]=3;
				dir[i+1][yy-1]=0;
				return 1;
			}
		}
		fr(i,x+1,xx){
			if(dir[i][yy-2]==3){
				dir[i][yy-2]=2;
				fr(j,i,xx-1) dir[j][yy-1]=1;
				dir[xx][yy-1]=2;
				fr(j,x+1,xx) dir[j][yy]=3;
				dir[x][yy]=0;
				fr(j,x,i-2) dir[j][yy-1]=1;
				dir[i-1][yy-1]=0;
				return 1;
			}
		}
	}
	if((yy-2)>=sty){
		if(yy==edy){
			if(edx<(xx-1)){
				dfs1(x,y,xx,yy-2,stx,sty,edx+2,edy-2);
				fr(i,x+1,edx) dir[i][yy]=3;
				dir[x][yy]=2;
				fr(i,x,edx) dir[i][yy-1]=1;
				dir[edx+1][yy-1]=0;
				fr(i,edx+1,xx-1) dir[i][yy]=1;
				dir[xx][yy]=2;
				fr(i,edx+3,xx) dir[i][yy-1]=3;
				dir[edx+2][yy-1]=2;
			}
			else{
				dfs1(x,y,xx,yy-2,stx,sty,edx-2,edy-2);
				fr(i,edx,xx-1) dir[i][yy]=1;
				dir[xx][yy]=2;
				fr(i,edx,xx) dir[i][yy-1]=3;
				dir[edx-1][yy-1]=0;
				fr(i,x+1,edx-1) dir[i][yy]=3;
				dir[x][yy]=2;
				fr(i,x,edx-3) dir[i][yy-1]=1;
				dir[edx-2][yy-1]=2;
			}
		}
		else{
			if(edx<xx){
				dfs1(x,y,xx,yy-2,stx,sty,edx+1,edy-1);
				fr(i,x+1,edx) dir[i][yy-1]=3;
				dir[x][yy-1]=0;
				fr(i,x,xx-1) dir[i][yy]=1;
				dir[xx][yy]=2;
				fr(i,edx+2,xx) dir[i][yy-1]=3;
				dir[edx+1][yy-1]=2;
			}
			else{
				dfs1(x,y,xx,yy-2,stx,sty,edx-1,edy-1);
				fr(i,edx,xx-1) dir[i][yy-1]=1;
				dir[xx][yy-1]=0;
				fr(i,x+1,xx) dir[i][yy]=3;
				dir[x][yy]=2;
				fr(i,x,edx-2) dir[i][yy-1]=1;
				dir[edx-1][yy-1]=2;
			}
		}
		return 1;
	}
	return 0;
}
int main(){
	n=read();
	m=read();
	ll stx=read(),sty=read(),edx=read(),edy=read();
	bl ck1=0,ck2=0;
	if(stx>edx){
		swap(stx,edx);
		ck1=1;
	}
	if(sty>edy){
		swap(sty,edy);
		ck2=1;
	}
	if(n*m%2==0&&(stx+sty)%2==(edx+edy)%2){
		pf("NIE");
		return 0;
	}
	if(n*m%2==1&&(stx+sty)%2!=(edx+edy)%2){
		pf("NIE");
		return 0;
	}
	dfs1(1,1,n,m,stx,sty,edx,edy);
	ll x=stx,y=sty;
	while(x!=edx||y!=edy){
		ll o=dir[x][y],nx=x+d[o][0],ny=y+d[o][1];
		if(ck1&&(o&1)) o^=2;
		if(ck2&&!(o&1)) o^=2;
		if(!o) pc('G');
		else if(o==1) pc('P');
		else if(o==2) pc('D');
		else pc('L');
		x=nx;
		y=ny;
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 4
1 1
1 4

output:

PPPDDDLGGLLDPDL

result:

ok correct path

Test #2:

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

input:

4 4
3 2
2 3

output:

NIE

result:

ok no solution

Test #3:

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

input:

5 5
1 2
1 4

output:

NIE

result:

ok no solution

Test #4:

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

input:

6 6
1 1
1 4

output:

DPGPPPPDDDDDLGGGGLLDPDDDLLLGPPGLGLD

result:

ok correct path

Test #5:

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

input:

4 5
2 3
3 5


output:

GGLDDDDPGPGGGPDDDDL

result:

ok correct path

Test #6:

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

input:

4 6
1 2
2 5

output:

NIE

result:

ok no solution

Test #7:

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

input:

6 6
1 5
4 5

output:

DPGGLGGGPDDPGGPPPDLLDPPDDDLGGLLDDPG

result:

ok correct path

Test #8:

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

input:

38 6
33 5
36 5

output:

LGGGGLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLDDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPPPGGLGGGPDDPGGPPPDLLDPPDDDLGGLLDDPG

result:

ok correct path

Test #9:

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

input:

57 6
26 3
29 5

output:

GGLLLLLLLLLLLLLLLLLLLLLLLLLDDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGPGGGPDDDDLDPPPGGPPDLDPPGGGLLLGPPPPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPDDDDPGGGGPD...

result:

ok correct path

Test #10:

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

input:

64 126
45 13
48 15


output:

GGGGGGGGGGGGPDDDDDDDDDDDDDLLGGGGGGGGGGGGGLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDPGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG...

result:

ok correct path

Test #11:

score: -100
Wrong Answer
time: 2ms
memory: 3324kb

input:

64 32
35 13
48 15


output:

NIE

result:

wrong answer you didn't find a solution but jury did