QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#42849#4432. Jungle Trailfecto_elfilisAC ✓137ms35264kbC++1.4kb2022-08-04 12:25:002022-08-04 12:25:02

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-04 12:25:02]
  • Judged
  • Verdict: AC
  • Time: 137ms
  • Memory: 35264kb
  • [2022-08-04 12:25:00]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
const int N=2010;
int t,n,m,r[N],c[N],ans[N*2],nx[N][N],mp[N][N];
char s[N];
int main () {
	scanf("%d",&t);
	for (int ii=1;ii<=t;ii++) {
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++) {r[i]=0;}
		for (int i=1;i<=m;i++) {c[i]=0;}
		for (int i=1;i<=n+m-2;i++) {ans[i]=0;}
		for (int i=1;i<=n;i++) {
			scanf("%s",s+1);
			for (int j=1;j<=m;j++) {nx[i][j]=-1,mp[i][j]=(s[j]=='.'?0:(s[j]=='#'?1:(s[j]=='O'?2:3)));}
		}
		for (int i=n;i>=1;i--) {
			for (int j=m;j>=1;j--) {
				if (i==n&&j==m) {nx[i][j]=0;}
				else if (mp[i][j]!=1) {
					if (i<n&&nx[i+1][j]>=0) {nx[i][j]=i+1;}
					if (j<m&&nx[i][j+1]>=0) {nx[i][j]=j+1+n;}
				}
			}
		}
		if (nx[1][1]==-1) {printf("NIE\n");continue;}
		int curx=1,cury=1,cnt=0;
		if (mp[1][1]==3) {r[1]=1;}
		while (curx!=n||cury!=m) {
			if (nx[curx][cury]<=n) {
				curx++;
				if ((mp[curx][cury]==3&&!c[cury])||(mp[curx][cury]==2&&c[cury])) {r[curx]=1;}
				ans[++cnt]=1;
			} else {
				cury++;
				if ((mp[curx][cury]==3&&!r[curx])||(mp[curx][cury]==2&&r[curx])) {c[cury]=1;}
				ans[++cnt]=0;
			}
		}
		printf("TAK\n");
		for (int i=1;i<=n;i++) {printf("%c",r[i]?'T':'N');}
		putchar('\n');
		for (int i=1;i<=m;i++) {printf("%c",c[i]?'T':'N');}
		putchar('\n');
		for (int i=1;i<=cnt;i++) {printf("%c",ans[i]?'D':'P');}
		putchar('\n');
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 137ms
memory: 35264kb

input:

486
4 5
..#..
@@O@@
##@#O
..@.@
2 2
OO
OO
2 2
@@
@@
2 2
@@
#@
2 2
@O
#@
2 2
@@
OO
2 2
O#
@O
2 2
@#
#@
2 2
@.
.@
2 2
@#
.O
2 2
OO
.O
10 10
@O@O#O@@@#
OO#@#@@#OO
#@#@#O##O@
OO##@@O#@O
O##@@#@O#@
OO@OO@@@O@
@O#@#@O#@O
@OOOOO@##.
O@OOO##O@@
OO@@OOOO#@
10 10
@@#OOO#O@@
#@@OO@@.O@
#.O@@O#@@O
OO@@#O@#O@
.#...

output:

TAK
NTNT
NNTNN
PDPPPDD
TAK
NN
NN
PD
TAK
TT
NN
PD
TAK
TT
NN
PD
TAK
TN
NT
PD
TAK
TN
NN
PD
TAK
NT
NT
DP
NIE
TAK
TT
NN
PD
TAK
TN
NN
DP
TAK
NN
NN
PD
NIE
TAK
TTNTTNNNNT
NNNTTNNNTN
PDPPPPPPPDDDDDPDDD
TAK
NNNTTTNTNN
NNTNTNTNTN
PPDDDPPDPDPPDDPDPD
TAK
NNNNTTTTTN
NNNTTNTTNN
PPDDPPPDPDPPDDPDDD
TAK
NTTTNNNTNT
NT...

result:

ok ac (486 test cases)

Extra Test:

score: 0
Extra Test Passed