QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#877675 | #7696. Forest for the Trees | WeaRD276 | WA | 113ms | 3712kb | C++20 | 2.8kb | 2025-02-01 00:37:08 | 2025-02-01 00:37:17 |
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;
int solve()
{
int n, m, r;
if (!(cin >> n >> m >> r))
return 1;
vector<pii> tr(n), de(m);
FOR (i, 0, n)
cin >> tr[i].x >> tr[i].y;
FOR (i, 0, m)
cin >> de[i].x >> de[i].y;
//sort(all(tr));
sort(all(de));
int x0 = de[0].x, y0 = de[0].y;
array<int, 3> ans{-1, -1, -1};
auto check = [&](int px, int py, int d) -> bool
{
//cerr << "x = " << px << " y = " << py << '\n';
int cnt = 0;
for (const pii& tree: tr)
{
int x = tree.x - px, y = tree.y - py;
if (abs(x - px) + abs(y - py) > r)
continue;
int cx, cy;
if (d == 0)
{
cx = x;
cy = y;
}
else if (d == 1)
{
cx = -x;
cy = -y;
}
else if (d == 2)
{
cx = -y;
cy = x;
}
else
{
cx = y;
cy = -x;
}
pii pos = {cx, cy};
auto it = lower_bound(all(de), pos);
if (it == de.end() || *it != pos)
return false;
cnt++;
}
return cnt == m;
};
for (const pii& tree: tr)
{
int x = tree.x, y = tree.y;
FOR (d, 0, 4)
{
int cx, cy;
if (d == 0)
{
cx = x - x0;
cy = y - y0;
}
else if (d == 1)
{
cx = x + x0;
cy = y + y0;
}
else if (d == 2)
{
cx = x - y0;
cy = y + x0;
}
else
{
cx = x + y0;
cy = y - x0;
}
//cerr << "x = " << cx << " y = " << cy << '\n';
if (check(cx, cy, d))
{
array<int, 3> cur{cx, cy, d};
if (ans != array<int, 3>{-1, -1, -1} && ans != cur)
{
cout << "Ambiguous\n";
return 0;
}
ans = cur;
}
}
}
if (ans == array<int, 3>{-1, -1, -1})
cout << "Impossible\n";
else
cout << ans[0] << ' ' << ans[1] << '\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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
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: 3584kb
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
Wrong Answer
time: 113ms
memory: 3712kb
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 ...
output:
Impossible
result:
wrong answer 1st lines differ - expected: '-9929 -9959', found: 'Impossible'