QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352184 | #5473. Move One Coin | warner1129# | RE | 356ms | 11444kb | C++20 | 4.7kb | 2024-03-12 22:51:54 | 2024-03-12 22:51:57 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
template <ranges::range T,
class = enable_if_t<!is_convertible_v<T, string_view>>>
istream &operator>>(istream &s, T &&v) {
for (auto &&x : v)
s >> x;
return s;
}
template <ranges::range T,
class = enable_if_t<!is_convertible_v<T, string_view>>>
ostream &operator<<(ostream &s, T &&v) {
for (auto &&x : v)
s << x << ' ';
return s;
}
#ifdef LOCAL
template <class... T> void dbg(T... x) {
char e{};
((cerr << e << x, e = ' '), ...);
}
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
template <class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
template <class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template <class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
constexpr i64 mod = 998244353;
void solve() {
auto Read = [&]() -> vector<pair<int, int>> {
int r, c;
cin >> r >> c;
vector<string> G(r);
cin >> G;
vector<pair<int, int>> V;
for (int i = 0; i < r; i++)
for (int j = 0; j < c; j++)
if (G[i][j] == 'o') {
V.emplace_back(i, j);
}
return V;
};
auto A = Read();
auto B = Read();
sort(all(A));
sort(all(B));
auto Rotate = [](auto &V) -> void {
for (auto &[x, y] : V) {
tie(x, y) = pair{-y, x};
}
};
auto get = [](const auto &A) -> vector<pair<int, int>> {
vector<pair<int, int>> R;
for (auto p : A) {
R.push_back(p);
if (R.size() >= 3) break;
}
for (auto p : A | views::reverse) {
R.push_back(p);
if (R.size() >= 3) break;
}
return R;
};
auto shi = [](auto V, pair<int, int> b) {
for (auto &[x, y] : V) {
x -= b.ff;
y -= b.ss;
}
return V;
};
auto pB = get(B);
for (int t = 0; t < 4; t++) {
Rotate(A);
auto pA = get(A);
for (auto p : pA)
for (auto q : pB) {
auto U = shi(A, p);
auto V = shi(B, q);
sort(all(U));
sort(all(V));
vector<bool> matU(U.size()), matV(V.size());
for (int i = 0, j = 0; i < U.size(); i++) {
while (j < V.size() and V[j] < U[i]) {
j++;
}
if (j < V.size() and U[i] == V[j]) {
matU[i] = matV[j] = 1;
}
}
for (int i = 0, j = 0; i < V.size(); i++) {
while (j < U.size() and U[j] < V[i]) {
j++;
}
if (j < U.size() and V[i] == U[j]) {
matV[i] = matU[j] = 1;
}
}
if (ranges::count(matU, 0) == 1 and ranges::count(matV, 0) == 1) {
pair<int, int> fr, to;
for (int i = 0; i < U.size(); i++)
if (matU[i] == 0) {
fr = U[i];
break;
}
for (int i = 0; i < V.size(); i++)
if (matV[i] == 0) {
to = V[i];
break;
}
fr.ff += p.ff;
fr.ss += p.ss;
to.ff += p.ff;
to.ss += p.ss;
for (int g = t + 1; g < 4; g++) {
tie(fr.ff, fr.ss) = pair{-fr.ss, fr.ff};
tie(to.ff, to.ss) = pair{-to.ss, to.ff};
}
swap(fr.ff, fr.ss);
swap(to.ff, to.ss);
cout << fr.ff << ' ' << fr.ss << '\n';
cout << to.ff << ' ' << to.ss << '\n';
return;
}
}
}
assert(0);
}
signed main() {
cin.tie(0)->sync_with_stdio(false);
cin.exceptions(cin.failbit);
int T = 1;
// cin >> T;
while (T--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3868kb
input:
2 3 xox ooo 4 2 ox ox ox ox
output:
1 0 -1 1
result:
ok OK! rot=1
Test #2:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
3 3 xox oxo xox 4 4 oxxx xxox xoxo xxxx
output:
0 1 3 -1
result:
ok OK! rot=1
Test #3:
score: 0
Accepted
time: 1ms
memory: 4120kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
498 499 996 997
result:
ok OK! rot=2
Test #4:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #5:
score: 0
Accepted
time: 1ms
memory: 3924kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
499 0 996 -498
result:
ok OK! rot=2
Test #6:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 499 497 1
result:
ok OK! rot=0
Test #7:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 498 499 0
result:
ok OK! rot=1
Test #8:
score: 0
Accepted
time: 0ms
memory: 4148kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #9:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
500 500 xooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
1 1 499 499
result:
ok OK! rot=2
Test #10:
score: 0
Accepted
time: 0ms
memory: 4084kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=0
Test #11:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
500 500 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
499 1 997 -497
result:
ok OK! rot=1
Test #12:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
500 500 oxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
0 0 498 498
result:
ok OK! rot=1
Test #13:
score: 0
Accepted
time: 356ms
memory: 11444kb
input:
500 500 oooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooooo...
output:
429 80 483 173
result:
ok OK! rot=2
Test #14:
score: 0
Accepted
time: 277ms
memory: 6380kb
input:
302 302 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx...
output:
256 0 0 180
result:
ok OK! rot=0
Test #15:
score: -100
Runtime Error
input:
302 302 xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoxxxx...