QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#64065#5112. Where Am I?YaoBIGWA 25ms7808kbC++173.3kb2022-11-24 02:22:362022-11-24 02:22:39

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-24 02:22:39]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:7808kb
  • [2022-11-24 02:22:36]
  • 提交

answer

#include "bits/stdc++.h"
#define rep(i, a, n) for (auto i = a; i <= (n); ++i)
#define revrep(i, a, n) for (auto i = n; i >= (a); --i)
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if (b < a) { a = b; return 1; } return 0; }
using namespace std;

template<class A, class B> string to_string(const pair<A, B> &p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(const A &v) {
	bool first = 1;
	string res = "{";
	for (const auto &x: v) {
		if (!first) res += ", ";
		first = 0;
		res += to_string(x);
	}
	res += "}";
	return res;
}
template<class A, class B> string to_string(const pair<A, B> &p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug_out() { cerr << endl; }
template<class H, class... T> void debug_out(const H& h, const T&... t) {
	cerr << " " << to_string(h);
	debug_out(t...);
}
#ifndef ONLINE_JUDGE
	#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
	#define debug(...) if(0) puts("No effect.")
#endif

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;

pii operator +(pii a, pii b) { return {a.first + b.first, a.second + b.second}; }

int main() {
	ios::sync_with_stdio(0); cin.tie(0);

	int n, m; cin >> n >> m;
	vector<string> ss(m);
	for (auto &s: ss) cin >> s;
	vector<pii> marks;
	rep(j, 0, m - 1) rep(i, 0, n - 1) if (ss[j][i] == 'X') marks.emplace_back(i, m - 1 - j);

	const int off = 100;
	static int ids[off * 2 + 1][off * 2 + 1];
	pii now = {off, off};
	int cnt = 0;
	ids[off][off] = cnt++;
	rep(i, 1, off) {
		int len = i * 2;
		now = now + pii{-1, 1};
		rep(s, 1, len) {
			auto [x, y] = now + pii{s, 0};
			ids[x][y] = cnt++;
		}
		rep(s, 1, len) {
			auto [x, y] = now + pii{len, -s};
			ids[x][y] = cnt++;
		}
		rep(s, 1, len) {
			auto [x, y] = now + pii{len - s, -len};
			ids[x][y] = cnt++;
		}
		rep(s, 1, len) {
			auto [x, y] = now + pii{0, -len + s};
			ids[x][y] = cnt++;
		}
	}
	vvi as;
	rep(i, 0, n - 1) rep(j, 0, m - 1) {
		vi vec;
		for (auto it: marks) {
			auto [x, y] = it + pii{-i, -j};
			vec.push_back(ids[off + x][off + y]);
		}
		sort(all(vec));
		as.push_back(vec);
	}
	vi ps(n * m); iota(all(ps), 0);
	sort(all(ps), [&](int i, int j) { return as[i] < as[j]; });
	vi lcp(n * m);
	rep(ind, 0, n * m - 2) {
		int i = ps[ind];
		int j = ps[ind + 1];
		auto &v1 = as[i];
		auto &v2 = as[j];
		rep(k, 0, sz(v1) - 1) {
			if (v1[k] != v2[k]) {
				int mn = min(v1[k], v2[k]);
				chmax(lcp[i], mn);
				chmax(lcp[j], mn);
				break;
			}
		}
	}
	int s = accumulate(all(lcp), 0);
	auto mx = *max_element(all(lcp));
	vector<pii> ans;
	rep(i, 0, n * m - 1) if (lcp[i] == mx) ans.emplace_back(i / m, i % m);
	sort(all(ans), [](pii a, pii b) { return tie(a.second, a.first) < tie(b.second, b.second); });
	printf("%.3f\n", (double) s / (n * m));
	printf("%d\n", mx);
	for (auto [x, y]: ans) printf("(%d,%d) ", x + 1, y + 1);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3904kb

input:

1 1
X

output:

0.000
0
(1,1) 

result:

ok correct!

Test #2:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

score: 0
Accepted
time: 2ms
memory: 3832kb

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

score: 0
Accepted
time: 2ms
memory: 3904kb

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

2 1
XX

output:

3.000
3
(1,1) (2,1) 

result:

ok correct!

Test #7:

score: 0
Accepted
time: 2ms
memory: 3712kb

input:

3 3
XXX
X.X
XXX

output:

3.111
5
(3,1) (3,2) 

result:

ok correct!

Test #8:

score: 0
Accepted
time: 11ms
memory: 7144kb

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:

4757.947
9704
(50,1) (50,100) 

result:

ok correct!

Test #9:

score: 0
Accepted
time: 4ms
memory: 4000kb

input:

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

output:

19735.320
39599
(100,1) (100,2) 

result:

ok correct!

Test #10:

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

input:

100 100
....................................................................................................
....................................................................................................
.............................................................................................

output:

19865.670
39500
(100,1) (100,2) 

result:

ok correct!

Test #11:

score: 0
Accepted
time: 17ms
memory: 7808kb

input:

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

output:

11855.639
39302
(100,99) (99,100) 

result:

ok correct!

Test #12:

score: 0
Accepted
time: 25ms
memory: 7756kb

input:

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

output:

11854.610
39104
(1,99) (2,100) 

result:

ok correct!

Test #13:

score: -100
Wrong Answer
time: 2ms
memory: 4224kb

input:

20 73
...........X........
.X..................
....................
X.....X........X....
......X........X....
....................
....................
.X..................
....................
...........X........
.X..................
X...................
.......X........X...
.X....X........X....
...

output:

50.098
80
(7,6) (16,6) (20,12) (7,15) (16,15) (7,24) (16,24) (16,33) (7,33) (16,42) (7,42) (19,46) (20,47) (12,47) (7,51) (16,51) (12,56) (19,56) (7,60) (16,60) (20,65) (20,67) (7,69) (16,69) 

result:

wrong answer Read (16,33) but expected (7,33)