QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#131862 | #5135. Kiosk Construction | Yarema# | WA | 1ms | 3548kb | C++17 | 2.0kb | 2023-07-28 17:00:37 | 2023-07-28 17:00:39 |
Judging History
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;
}
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;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3484kb
input:
2 3 1 2 3 6 5 4
output:
2 2
result:
ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
3 3 1 4 8 7 5 2 3 9 6
output:
impossible
result:
ok
Test #3:
score: 0
Accepted
time: 1ms
memory: 3480kb
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: 3532kb
input:
2 2 1 2 3 4
output:
1 2
result:
ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
2 2 4 3 1 2
output:
4 2
result:
ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
2 3 3 5 2 6 1 4
output:
impossible
result:
ok
Test #7:
score: -100
Wrong Answer
time: 1ms
memory: 3544kb
input:
2 3 5 3 4 1 6 2
output:
5 3
result:
FAIL Reported distance is not correct.