QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94735#5605. A-Mazing PuzzlePetroTarnavskyi#WA 2102ms559360kbC++172.7kb2023-04-07 17:20:232023-04-07 17:20:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-07 17:20:26]
  • 评测
  • 测评结果:WA
  • 用时:2102ms
  • 内存:559360kb
  • [2023-04-07 17:20:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second

typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;

const int N = 54;
bool br[N][N];
bool bc[N][N];
int df = 0;
int n, m, e;

vector<PII> g[N * N * N * N];
int w[N * N * N * N];
int mn[N * N * N * N];

string dir = "SWNE";	

bool fin(int x1, int y1)
{
	return (y1 == 0 && x1 == e);
}
PII bl(int x1, int y1, int di)
{
	if(fin(x1, y1))
		return {x1, y1};
		
	if (di == 0) return {x1, y1 - !br[x1][y1 - 1]};
	if (di == 1) return {x1 - !bc[x1 - 1][y1], y1};
	if (di == 2) return {x1, y1 + !br[x1][y1]};
	if (di == 3) return {x1 + !bc[x1][y1], y1};
	assert(0);
}

int calc(int x1, int y1, int x2, int y2)
{
	return x1 * N * N * N + y1 * N * N + x2 * N + y2;
}

void build()
{
	FOR(x1, 1, n + 1) FOR(y1, 0, m + 1) FOR(x2, 1, n + 1) FOR(y2, 0, m + 1)
	{
		if (y1 == 0 && !fin(x1, y1)) continue;
		if (y2 == 0 && !fin(x2, y2)) continue;
		FOR(di, 0, 4)
		{
			auto [nx1, ny1] = bl(x1, y1, di);
			auto [nx2, ny2] = bl(x2, y2, (di + df) % 4);
			int bum = 0;
			if (x1 == nx1 && y1 == ny1 && !fin(x1, y1)) bum++;
			if (x2 == nx2 && y2 == ny2 && !fin(x2, y2)) bum++;
			if (bum == 2) continue;
			int X = calc(x1, y1, x2, y2);
			int Y = calc(nx1, ny1, nx2, ny2);
			g[X].PB({Y, bum});
		}
	}
}

const int INF = 1e9;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> e;
	int x1, y1, x2, y2;
	char c1, c2;
	cin >> x1 >> y1 >> c1 >> x2 >> y2 >> c2;
	int dir1 = 0;
	int dir2 = 0;
	FOR(i, 0, 4) if (dir[i] == c1) dir1 = i;
	FOR(i, 0, 4) if (dir[i] == c2) dir2 = i;
	df = (dir2 + 4 - dir1) % 4;
	int sz;
	cin >> sz;
	FOR(i, 0, sz)
	{
		int a, b;
		cin >> a >> b;
		br[a][b] = 1;
	}
	cin >> sz;
	FOR(i, 0, sz)
	{
		int a, b;
		cin >> a >> b;
		bc[a][b] = 1;
	}
	//cout << bc[3][4] << '\n';
	//cout << 3 + !bc[3][4] << '\n';
	//return 0;
	FOR(i, 0, n)
		if (i + 1 != e) br[i + 1][0] = 1;
	FOR(i, 0, m)
		bc[0][i + 1] = 1;
		
	build();
	
	int st = calc(x1, y1, x2, y2);
	FOR(i, 0, N * N * N * N) w[i] = INF;
	w[st] = 0;
	queue<int> q;
	q.push(st);
	while(!q.empty())
	{
		int v = q.front();
		q.pop();
		for (auto [to, b] : g[v])
		{
			if (w[to] > w[v] + 1)
			{
				q.push(to);
				w[to] = w[v] + 1;
				mn[to] = mn[v] + b;
			}
			if (w[to] == w[v] + 1)
				mn[to] = min(mn[to], mn[v] + b);
			
		}
	}
	int end = e * N * N * N + e * N;
	cout << w[end] << ' ' << mn[end] << '\n';
		
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 46ms
memory: 236200kb

input:

7 4 4
3 2 S 6 3 S
6 1 1 1 2 1 3 2 3 5 1 5 3
11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4

output:

8 1

result:

ok single line: '8 1'

Test #2:

score: 0
Accepted
time: 43ms
memory: 235996kb

input:

3 4 2
1 3 S 3 2 S
1 3 3
5 1 1 2 1 1 2 1 3 2 3

output:

7 2

result:

ok single line: '7 2'

Test #3:

score: 0
Accepted
time: 2102ms
memory: 559360kb

input:

50 50 4
15 28 W 9 43 E
49 11 47 42 33 3 4 36 49 21 21 15 34 43 5 32 35 3 21 7 1 40 4 22 44 11 40 46 43 13 26 32 6 44 25 31 46 26 7 45 4 18 10 10 21 3 20 31 8 34 40 42 1 48 43 18 17 9 39 17 2 48 25 39 35 45 43 8 2 22 17 6 46 33 1 38 6 28 25 29 32 45 12 11 20 8 48 14 9 2 24 45 38 1 20 34 5 46 24
50 13...

output:

91 52

result:

ok single line: '91 52'

Test #4:

score: 0
Accepted
time: 2039ms
memory: 558908kb

input:

50 50 25
1 50 N 50 50 E
1 45 25
1 16 37

output:

100 26

result:

ok single line: '100 26'

Test #5:

score: -100
Wrong Answer
time: 48ms
memory: 236924kb

input:

10 10 1
10 1 N 10 2 N
0
81 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 6 10 6 9 6 8 6 7 6 6 6 5 6 4 6 3 6 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 2 10 2 9 2 8 2 7 2...

output:

101 1

result:

wrong answer 1st lines differ - expected: '120 4', found: '101 1'