QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#876573 | #7696. Forest for the Trees | WeaRD276 | TL | 1ms | 3712kb | C++20 | 3.1kb | 2025-01-31 00:23:15 | 2025-01-31 00:23:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
struct pair_hash {
size_t operator()(const std::pair<int, int>& p) const {
return std::hash<int>()(p.first) ^ (std::hash<int>()(p.second) << 1);
}
};
int solve()
{
int n, m, r;
if (!(cin >> n >> m >> r))
return 1;
assert(n >= m);
unordered_set<pii, pair_hash> tr;
tr.reserve(1e3);
vector<pii> de(m);
FOR (i, 0, n)
{
int x, y;
cin >> x >> y;
tr.insert({x, y});
}
FOR (i, 0, m)
cin >> de[i].x >> de[i].y;
auto check = [&](pii pos, int d) -> bool
{
bool ok = 1;
unordered_set<pii, pair_hash>trees=tr;
FOR (i, 0, m)
{
pii cur;
// up
if (d == 0)
{
cur.x = pos.x + de[i].x;
cur.y = pos.y + de[i].y;
}
// down
if (d == 1)
{
cur.x = pos.x - de[i].x;
cur.y = pos.y - de[i].y;
}
if (d == 2)
{
cur.x = pos.x + de[i].y;
cur.y = pos.y - de[i].x;
}
// down
if (d == 3)
{
cur.x = pos.x - de[i].y;
cur.y = pos.y + de[i].x;
}
//cerr << cur.x << ' ' << cur.y << '\n';
ok &= (tr.find(cur) != tr.end());
if(!ok) return false;
if (abs(pos.x - cur.x) + abs(pos.y - cur.y) > r)
return false;
trees.erase({cur.x, cur.y});
}
for(auto [x, y]: trees)
{
if(abs(x-pos.x)+abs(y-pos.y) <= r)
return false;
}
return true;
};
vector<array<int, 3>> poses;
for (pii tree: tr)
{
int x = tree.x, y = tree.y;
FOR(d, 0, 4)
{
pii cur;
if (d == 0)
{
cur.x = x - de[0].x;
cur.y = y - de[0].y;
}
// down
if (d == 1)
{
cur.x = x + de[0].x;
cur.y = y + de[0].y;
}
if (d == 2)
{
cur.x = x - de[0].y;
cur.y = y + de[0].x;
}
// down
if (d == 3)
{
cur.x = x + de[0].y;
cur.y = y - de[0].x;
}
if (check(cur, d))
poses.pb({cur.x, cur.y, d});
}
}
sort(all(poses));
poses.erase(unique(all(poses)), poses.end());
if (sz(poses) == 1)
cout << poses[0][0] << ' ' << poses[0][1] << '\n';
else if (poses.empty())
cout << "Impossible\n";
else
cout << "Ambiguous\n";
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cerr << "_____________________________\n";
#endif
}
#ifdef ONPC
cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
#endif
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3584kb
input:
4 4 100 1 1 2 2 2 1 3 3 0 1 0 2 -1 2 -2 3
output:
0 1
result:
ok single line: '0 1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
4 4 4 0 1 1 0 0 -1 -1 0 0 1 1 0 0 -1 -1 0
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #3:
score: -100
Time Limit Exceeded
input:
4899 957 32 -9961 -9999 -9970 -9968 -9942 -9986 -9991 -9991 -9950 -9990 -9958 -9994 -9939 -9944 -9992 -9987 -9973 -9937 -9981 -9941 -9940 -9940 -9989 -9945 -9961 -9963 -9970 -9932 -9969 -9967 -9977 -9971 -9949 -9989 -9958 -9958 -9957 -9993 -9937 -9935 -9938 -9980 -9965 -9997 -9992 -9951 -9946 -9984 ...