QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#131861#5135. Kiosk ConstructionYarema#WA 1ms3588kbC++172.0kb2023-07-28 16:57:142023-07-28 16:57:15

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-28 16:57:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3588kb
  • [2023-07-28 16:57:14]
  • 提交

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
#define FILL(a, b) memset(a, b, sizeof(a))

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

const int INF = 1e9 + 7;

const int N = 47;

int a[N][N];
bool used[N][N];
int n, m;

vector<PII> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

bool ok(int x, int y)
{
	return x >= 0 && x < n && y >= 0 && y < m;
}

bool better(int fin, int now, int to, int to2)
{
	int d1 = abs(fin - to);
	int d2 = abs(fin - to2);
	if (d1 < d2) return false;
	if (d2 < d1) return true;
	d1 = abs(now - to);
	d2 = abs(now - to2);
	if (d1 < d2) return false;
	if (d2 < d1) return true;
	assert(0);
}

int X[N * N], Y[N * N];

int f(int x, int y, int c, int d)
{
	int dis = 0;
	while (x != c && y != d)
	{
		if (used[x][y] == 1) return INF;
		used[x][y] = 1;
		X[dis] = x;
		Y[dis] = y;
		int bx = -1, by = -1;
		FOR (i, 0, 4)
		{
			int nx = x + dir[i].F, ny = y + dir[i].S;
			if (ok(nx, ny))
			{
				if (bx == -1 || better(a[c][d], a[x][y], a[bx][by], a[nx][ny]))
					bx = nx, by = ny;
			}
		}
		dis++;
		x = bx;
		y = by;
	}
	FOR (i, 0, dis) used[X[i]][Y[i]] = 0;
	return dis + 1;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	FOR (i, 0, n) FOR (j, 0, m) cin >> a[i][j];
	
	int bv = -1, ans = INF;
	
	FOR (i, 0, n)
	{
		FOR (j, 0, m)
		{
			int mx = 0;
			FOR (tox, 0, n)
			{
				FOR (toy, 0, m)
				{
					mx = max(mx, f(i, j, tox, toy));
					if (mx == INF) break;
				}
				if (mx == INF) break;
			}
			if (mx < ans)
			{
				ans = mx;
				bv = a[i][j];
			}
		}
	}
	if (ans == INF)
		cout << "impossible\n";
	else
		cout << bv << ' ' << ans << '\n';
	
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3532kb

input:

2 3
1 2 3
6 5 4

output:

2 2

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3528kb

input:

3 3
1 4 8
7 5 2
3 9 6

output:

impossible

result:

ok 

Test #3:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

3 3
9 3 1
4 7 2
8 6 5

output:

4 3

result:

ok 

Test #4:

score: 0
Accepted
time: 1ms
memory: 3460kb

input:

2 2
1 2
3 4

output:

1 2

result:

ok 

Test #5:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

2 2
4 3
1 2

output:

4 2

result:

ok 

Test #6:

score: -100
Wrong Answer
time: 1ms
memory: 3532kb

input:

2 3
3 5 2
6 1 4

output:

6 2

result:

wrong answer Token "6" doesn't correspond to pattern "impossible"