QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#76397 | #3816. Home alone: Johnny lost in New York | AFewSuns | WA | 2ms | 3456kb | C++14 | 9.8kb | 2023-02-09 19:43:03 | 2023-02-09 19:43:07 |
Judging History
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){
dfs0(x,y,xx,yy,edx,edy,stx,sty,1);
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: 2ms
memory: 3380kb
input:
4 4 1 1 1 4
output:
PPPDDDLGGLLDPDL
result:
ok correct path
Test #2:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
4 4 3 2 2 3
output:
NIE
result:
ok no solution
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 3156kb
input:
5 5 1 2 1 4
output:
DD
result:
wrong answer expected no solution (NIE)