QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#76435 | #3816. Home alone: Johnny lost in New York | AFewSuns | RE | 0ms | 0kb | C++14 | 12.0kb | 2023-02-09 22:30:51 | 2023-02-09 22:30:52 |
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,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