QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#64064#5112. Where Am I?YaoBIGWA 18ms7804kbC++173.3kb2022-11-24 02:15:592022-11-24 02:16:00

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:16:00]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:7804kb
  • [2022-11-24 02:15:59]
  • 提交

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));
	vi ans;
	rep(i, 0, n * m - 1) if (lcp[i] == mx) ans.push_back(i);
	printf("%.3f\n", (double) s / (n * m));
	printf("%d\n", mx);
	for (auto i: ans) {
		int x = i / m;
		int y = i % m;
		printf("(%d,%d) ", x + 1, y + 1);
	}
	puts("");
	return 0;
}

詳細信息

Test #1:

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

input:

1 1
X

output:

0.000
0
(1,1) 

result:

ok correct!

Test #2:

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

input:

2 1
.X

output:

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

result:

ok correct!

Test #3:

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

input:

2 1
X.

output:

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

result:

ok correct!

Test #4:

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

input:

1 2
.
X

output:

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

result:

ok correct!

Test #5:

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

input:

1 2
X
.

output:

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

result:

ok correct!

Test #6:

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

input:

2 1
XX

output:

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

result:

ok correct!

Test #7:

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

input:

3 3
XXX
X.X
XXX

output:

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

result:

ok correct!

Test #8:

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

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: 4308kb

input:

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

output:

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

result:

ok correct!

Test #10:

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

input:

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

output:

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

result:

ok correct!

Test #11:

score: -100
Wrong Answer
time: 18ms
memory: 7804kb

input:

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

output:

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

result:

wrong answer Read (99,100) but expected (100,99)