QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#88753#5112. Where Am I?ItsJerrWA 10ms6156kbC++142.6kb2023-03-17 00:10:282023-03-17 00:10:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-17 00:10:31]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:6156kb
  • [2023-03-17 00:10:28]
  • 提交

answer

//source: https://qoj.ac/contest/1050/problem/5112

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

typedef long long ll;

map<pair<int, int>, int> idx;
void prep() {
	int px = 0, py = 0, it = 0;
	idx[make_pair(0, 0)] = 0;
	for (int layer = 1; layer <= 100; ++layer) {
		--px;
		idx[make_pair(px, py)] = ++it;
		for (int i = 1; i < 2 * layer; ++i) idx[make_pair(px, ++py)] = ++it;
		for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(++px, py)] = ++it;
		for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(px, --py)] = ++it;
		for (int i = 1; i <= 2 * layer; ++i) idx[make_pair(--px, py)] = ++it;
	}
}

const int N = 110;
char a[N][N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	if (fopen("icpc_wf_f.inp", "r")) {
		freopen("icpc_wf_f.inp", "r", stdin);
		freopen("icpc_wf_f.out", "w", stdout);
	}

#ifdef LOCAL_MACHINE
	if (fopen("task.inp", "r")) {
		freopen("task.inp", "r", stdin);
		freopen("task.out", "w", stdout);
	}
#endif

	prep();

	int m, n; cin >> n >> m;
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) cin >> a[i][j];

	vector<pair<int, int>> marked;
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) if (a[i][j] == 'X') marked.emplace_back(i, j);

	vector<tuple<vector<int>, int, int>> v;
	for (int i = 1; i <= m; ++i) for (int j = 1; j <= n; ++j) {
			vector<int> cur;
			for (const pair<int, int> &p : marked) {
				int u, v; tie(u, v) = p;
				cur.push_back(idx[make_pair(u - i, v - j)]);
			}
			sort(cur.begin(), cur.end());
			v.emplace_back(cur, i, j);
		}

	sort(v.begin(), v.end());

	int res = 0, mx = 0;
	vector<pair<int, int>> points;

	for (int i = 0; i < m * n; ++i) {
		int cur = 0, ans = 0;
		if (i) {
			for (int t = 0; t < marked.size(); ++t) {
				if (get<0>(v[i])[t] == get<0>(v[i - 1])[t]) ++cur;
			}
			ans = max(ans, min(get<0>(v[i])[cur], get<0>(v[i - 1])[cur]));
		}
		cur = 0;
		if (i + 1 < m * n) {
			for (int t = 0; t < marked.size(); ++t) {
				if (get<0>(v[i])[t] == get<0>(v[i + 1])[t]) ++cur;
			}
			ans = max(ans, min(get<0>(v[i])[cur], get<0>(v[i + 1])[cur]));
		}
		if (ans > mx) {
			mx = ans;
			points.clear();
		}
		if (ans == mx) points.emplace_back(get<2>(v[i]), n - get<1>(v[i]) + 1);

		res += ans;
	}

	cout << fixed << setprecision(3) << 1.0 * res / (m * n) << "\n";
	cout << mx << "\n";
	sort(points.begin(), points.end(), [&](const pair<int, int> &x, const pair<int, int> &y){
		if (x.second == y.second) return x.first < y.first;
		return x.second < y.second;
	});
	for (const pair<int, int> &i : points) cout << "(" << i.first << "," << i.second << ") ";
}

// ඞඞඞඞඞ you sus

详细

Test #1:

score: 100
Accepted
time: 5ms
memory: 6152kb

input:

1 1
X

output:

0.000
0
(1,1) 

result:

ok correct!

Test #2:

score: -100
Wrong Answer
time: 10ms
memory: 6156kb

input:

2 1
.X

output:

0.000
0
(1,2) (2,2) 

result:

wrong answer Read (1,2) but expected (1,1)