QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#64064 | #5112. Where Am I? | YaoBIG | WA | 18ms | 7804kb | C++17 | 3.3kb | 2022-11-24 02:15:59 | 2022-11-24 02:16:00 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)