QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88755#5112. Where Am I?ItsJerrWA 113ms10560kbC++142.6kb2023-03-17 00:13:042023-03-17 00:13:05

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:13:05]
  • 评测
  • 测评结果:WA
  • 用时:113ms
  • 内存:10560kb
  • [2023-03-17 00:13:04]
  • 提交

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 <= 120; ++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]), m - get<1>(v[i]) + 1);

		res += ans;
	}

	cout << fixed << setprecision(5) << 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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 14ms
memory: 7252kb

input:

1 1
X

output:

0.00000
0
(1,1) 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 3ms
memory: 7376kb

input:

2 1
.X

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #3:

score: 0
Accepted
time: 15ms
memory: 7260kb

input:

2 1
X.

output:

0.00000
0
(1,1) (2,1) 

result:

ok correct!

Test #4:

score: 0
Accepted
time: 8ms
memory: 7260kb

input:

1 2
.
X

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #5:

score: 0
Accepted
time: 8ms
memory: 7244kb

input:

1 2
X
.

output:

0.00000
0
(1,1) (1,2) 

result:

ok correct!

Test #6:

score: 0
Accepted
time: 10ms
memory: 7256kb

input:

2 1
XX

output:

3.00000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 14ms
memory: 7348kb

input:

3 3
XXX
X.X
XXX

output:

3.11111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: -100
Wrong Answer
time: 113ms
memory: 10560kb

input:

100 100
..X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X....X..
....................................................................................................
X............................................................................................

output:

4880.51110
9950
(3,1) (3,100) 

result:

wrong answer read 4880.511100 but expected 4757.947100, error = 122.564000