QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#76435#3816. Home alone: Johnny lost in New YorkAFewSunsRE 0ms0kbC++1412.0kb2023-02-09 22:30:512023-02-09 22:30:52

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 22:30:52]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-02-09 22:30:51]
  • 提交

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,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);
il void work(ll x,ll y,ll k,bl t){
	if(!t) dir[x][y]=k;
	else dir[x+d[k][0]][y+d[k][1]]=k^2;
}
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;
}
bl dfs1(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	if(stx==edx&&sty==edy) return 0;
	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 1;
	}
	if((xx-x+1)>5){
		if(doleft(x,y,xx,yy,stx,sty,edx,edy)) return 1;
		if(doright(x,y,xx,yy,stx,sty,edx,edy)) return 1;
	}
	if((yy-y+1)>5){
		if(doup(x,y,xx,yy,stx,sty,edx,edy)) return 1;
		if(dodown(x,y,xx,yy,stx,sty,edx,edy)) return 1;
	}
	return 0;
}
bl doleft(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	ll nx=stx,ny=sty,t=0;
	if(stx>edx){
		nx=edx;
		ny=edy;
		t=1;
	}
	if(nx>=(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)<=(stx+edx-nx)){
		if(x==nx){
			if(ny>(y+1)){
				if(dfs1(x+2,y,xx,yy,stx+2*(!t),sty-2*(!t),edx+2*t,edy-2*t)){
					fr(i,ny,yy-1) work(x,i,2,t);
					work(x,yy,1,t);
					fr(i,ny,yy) work(x+1,i,0,t);
					work(x+1,ny-1,3,t);
					fr(i,y+1,ny-1) work(x,i,0,t);
					work(x,y,1,t);
					fr(i,y,ny-3) work(x+1,i,2,t);
					work(x+1,ny-2,1,t);
					return 1;
				}
			}
			else{
				if(dfs1(x+2,y,xx,yy,stx+2*(!t),sty+2*(!t),edx+2*t,edy+2*t)){
					fr(i,y+1,ny) work(x,i,0,t);
					work(x,y,1,t);
					fr(i,y,ny) work(x+1,i,2,t);
					work(x+1,ny+1,3,t);
					fr(i,ny+1,yy-1) work(x,i,2,t);
					work(x,yy,1,t);
					fr(i,ny+3,yy) work(x+1,i,0,t);
					work(x+1,ny+2,1,t);
					return 1;
				}
			}
		}
		else{
			if(ny>y){
				if(dfs1(x+2,y,xx,yy,stx+(!t),sty-(!t),edx+t,edy-t)){
					fr(i,ny,yy-1) work(x+1,i,2,t);
					work(x+1,yy,3,t);
					fr(i,y+1,yy) work(x,i,0,t);
					work(x,y,1,t);
					fr(i,y,ny-2) work(x+1,i,2,t);
					work(x+1,ny-1,1,t);
					return 1;
				}
			}
			else{
				if(dfs1(x+2,y,xx,yy,stx+(!t),sty+(!t),edx+t,edy+t)){
					fr(i,y+1,ny) work(x+1,i,0,t);
					work(x+1,y,3,t);
					fr(i,y,yy-1) work(x,i,2,t);
					work(x,yy,1,t);
					fr(i,ny+2,yy) work(x+1,i,0,t);
					work(x+1,ny+1,1,t);
					return 1;
				}
			}
		}
	}
	return 0;
}
bl doright(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	ll nx=stx,ny=sty,t=0;
	if(stx<edx){
		nx=edx;
		ny=edy;
		t=1;
	}
	if(nx<=(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+edx-nx)){
		if(xx==nx){
			if(ny<(yy-1)){
				if(dfs1(x,y,xx-2,yy,stx-2*(!t),sty+2*(!t),edx-2*t,edy+2*t)){
					fr(i,y+1,ny) work(xx,i,0,t);
					work(xx,y,3,t);
					fr(i,y,ny) work(xx-1,i,2,t);
					work(xx-1,ny+1,1,t);
					fr(i,ny+1,yy-1) work(xx,i,2,t);
					work(xx,yy,3,t);
					fr(i,ny+3,yy) work(xx-1,i,0,t);
					work(xx-1,ny+2,3,t);
					return 1;
				}
			}
			else{
				if(dfs1(x,y,xx-2,yy,stx-2*(!t),sty-2*(!t),edx-2*t,edy-2*t)){
					fr(i,ny,yy-1) work(xx,i,2,t);
					work(xx,yy,3,t);
					fr(i,ny,yy) work(xx-1,i,0,t);
					work(xx-1,ny-1,1,t);
					fr(i,y+1,ny-1) work(xx,i,0,t);
					work(xx,y,3,t);
					fr(i,y,ny-3) work(xx-1,i,2,t);
					work(xx-1,ny-2,3,t);
					return 1;
				}
			}
		}
		else{
			if(ny<yy){
				if(dfs1(x,y,xx-2,yy,stx-(!t),sty+(!t),edx-t,edy+t)){
					fr(i,y+1,ny) work(xx-1,i,0,t);
					work(xx-1,y,1,t);
					fr(i,y,yy-1) work(xx,i,2,t);
					work(xx,yy,3,t);
					fr(i,ny+2,yy) work(xx-1,i,0,t);
					work(xx-1,ny+1,3,t);
					return 1;
				}
			}
			else{
				if(dfs1(x,y,xx-2,yy,stx-(!t),sty-(!t),edx-t,edy-t)){
					fr(i,ny,yy-1) work(xx-1,i,2,t);
					work(xx-1,yy,1,t);
					fr(i,y+1,yy) work(xx,i,0,t);
					work(xx,y,3,t);
					fr(i,y,ny-2) work(xx-1,i,2,t);
					work(xx-1,ny-1,3,t);
					return 1;
				}
			}
		}
	}
	return 0;
}
bl doup(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	ll nx=stx,ny=sty,t=0;
	if(sty>edy){
		nx=edx;
		ny=edy;
		t=1;
	}
	if(ny>=(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)<=(sty+edy-ny)){
		if(y==ny){
			if(nx>(x+1)){
				if(dfs1(x,y+2,xx,yy,stx-2*(!t),sty+2*(!t),edx-2*t,edy+2*t)){
					fr(i,nx,xx-1) work(i,y,1,t);
					work(xx,y,2,t);
					fr(i,nx,xx) work(i,y+1,3,t);
					work(nx-1,y+1,0,t);
					fr(i,x+1,nx-1) work(i,y,3,t);
					work(x,y,2,t);
					fr(i,x,nx-3) work(i,y+1,1,t);
					work(nx-2,y+1,2,t);
					return 1;
				}
			}
			else{
				if(dfs1(x,y+2,xx,yy,stx+2*(!t),sty+2*(!t),edx+2*t,edy+2*t)){
					fr(i,x+1,nx) work(i,y,3,t);
					work(x,y,2,t);
					fr(i,x,nx) work(i,y+1,1,t);
					work(nx+1,y+1,0,t);
					fr(i,nx+1,xx-1) work(i,y,1,t);
					work(xx,y,2,t);
					fr(i,nx+3,xx) work(i,y+1,3,t);
					work(nx+2,y+1,2,t);
					return 1;
				}
			}
		}
		else{
			if(nx>x){
				if(dfs1(x,y+2,xx,yy,stx-(!t),sty+(!t),edx-t,edy+t)){
					fr(i,nx,xx-1) work(i,y+1,1,t);
					work(xx,y+1,0,t);
					fr(i,x+1,xx) work(i,y,3,t);
					work(x,y,2,t);
					fr(i,x,nx-2) work(i,y+1,1,t);
					work(nx-1,y+1,2,t);
					return 1;
				}
			}
			else{
				if(dfs1(x,y+2,xx,yy,stx+(!t),sty+(!t),edx+t,edy+t)){
					fr(i,x+1,nx) work(i,y+1,3,t);
					work(x,y+1,0,t);
					fr(i,x,xx-1) work(i,y,1,t);
					work(xx,y,2,t);
					fr(i,nx+2,xx) work(i,y+1,3,t);
					work(nx+1,y+1,2,t);
					return 1;
				}
			}
		}
	}
	return 0;
}
bl dodown(ll x,ll y,ll xx,ll yy,ll stx,ll sty,ll edx,ll edy){
	ll nx=stx,ny=sty,t=0;
	if(sty<edy){
		nx=edx;
		ny=edy;
		t=1;
	}
	if(ny<=(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+edy-ny)){
		if(yy==ny){
			if(nx<(xx-1)){
				if(dfs1(x,y,xx,yy-2,stx+2*(!t),sty-2*(!t),edx+2*t,edy-2*t)){
					fr(i,x+1,nx) work(i,yy,3,t);
					work(x,yy,0,t);
					fr(i,x,nx) work(i,yy-1,1,t);
					work(nx+1,yy-1,2,t);
					fr(i,nx+1,xx-1) work(i,yy,1,t);
					work(xx,yy,0,t);
					fr(i,nx+3,xx) work(i,yy-1,3,t);
					work(nx+2,yy-1,0,t);
					return 1;
				}
			}
			else{
				if(dfs1(x,y,xx,yy-2,stx-2*(!t),sty-2*(!t),edx-2*t,edy-2*t)){
					fr(i,nx,xx-1) work(i,yy,1,t);
					work(xx,yy,0,t);
					fr(i,nx,xx) work(i,yy-1,3,t);
					work(nx-1,yy-1,2,t);
					fr(i,x+1,nx-1) work(i,yy,3,t);
					work(x,yy,0,t);
					fr(i,x,nx-3) work(i,yy-1,1,t);
					work(nx-2,yy-1,0,t);
					return 1;
				}
			}
		}
		else{
			if(nx<xx){
				if(dfs1(x,y,xx,yy-2,stx+(!t),sty-(!t),edx+t,edy-t)){
					fr(i,x+1,nx) work(i,yy-1,3,t);
					work(x,yy-1,2,t);
					fr(i,x,xx-1) work(i,yy,1,t);
					work(xx,yy,0,t);
					fr(i,nx+2,xx) work(i,yy-1,3,t);
					work(nx+1,yy-1,0,t);
					return 1;
				}
			}
			else{
				if(dfs1(x,y,xx,yy-2,stx-(!t),sty-(!t),edx-t,edy-t)){
					fr(i,nx,xx-1) work(i,yy-1,1,t);
					work(xx,yy-1,2,t);
					fr(i,x+1,xx) work(i,yy,3,t);
					work(x,yy,0,t);
					fr(i,x,nx-2) work(i,yy-1,1,t);
					work(nx-1,yy-1,0,t);
					return 1;
				}
			}
		}
	}
	return 0;
}
void print(ll stx,ll sty,ll edx,ll edy){
	fr(i,1,n){
		write(i);
		if(i<10) pf("    ");
		else if(i<100) pf("   ");
		else pf("  ");
	}
	enter;
	fr(j,1,m){
		fr(i,1,n){
			if(i==stx&&j==sty) pf("S");
			else if(i==edx&&j==edy) pf("T");
			else pf("o");
			if(i<n&&dir[i][j]==1&&(i!=edx||j!=edy)) pf("--->");
			else if(i<n&&dir[i+1][j]==3&&((i+1)!=edx||j!=edy)) pf("<---");
			else pf("    ");
		}
		enter;
		if(j<m){
			fr(i,1,n){
				if(dir[i][j]==2&&(i!=edx||j!=edy)) pf("|");
				else if(dir[i][j+1]==0&&(i!=edx||(j+1)!=edy)) pf("^");
				else pf(" ");
				if(i<n) pf("    ");
			}
			enter;
			fr(i,1,n){
				if(dir[i][j]==2&&(i!=edx||j!=edy)) pf("v");
				else if(dir[i][j+1]==0&&(i!=edx||(j+1)!=edy)) pf("|");
				else pf(" ");
				if(i<n) pf("    ");
			}
			enter;
		}
	}
}
int main(){
	freopen("wa.out","w",stdout);
	n=read();
	m=read();
	ll stx=read(),sty=read(),edx=read(),edy=read();
	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);
//	print(stx,sty,edx,edy);
	fr(i,1,n) fr(j,1,m) ck[i][j]=0;
	ll x=stx,y=sty,cnt=0;
	while(x!=edx||y!=edy){
		ck[x][y]=1;
		ll o=dir[x][y],nx=x+d[o][0],ny=y+d[o][1];
		if(!o) pc('G');
		else if(o==1) pc('P');
		else if(o==2) pc('D');
		else pc('L');
		x=nx;
		y=ny;
		cnt++;
	}
//	fr(i,1,n) fr(j,1,m) if(!ck[i][j]) pf("%lld %lld\n",i,j);
	assert(cnt==(n*m-1));
}
/*
509 575
165 337
197 9
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

4 4
1 1
1 4

output:


result: