QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#877184 | #7696. Forest for the Trees | LaVuna47 | AC ✓ | 224ms | 43600kb | C++20 | 4.8kb | 2025-01-31 20:11:32 | 2025-01-31 20:11:32 |
Judging History
answer
//A tree without skin will surely die.
//A man without face is invincible.
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
namespace std
{
// Define a hash function for std::pair
template<typename T>
inline void hash_combine(std::size_t &seed, const T &v)
{
seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template<typename T1, typename T2>
struct hash<std::pair<T1, T2>>
{
std::size_t operator()(const std::pair<T1, T2> &key) const
{
std::size_t seed = 0;
hash_combine(seed, key.first);
hash_combine(seed, key.second);
return seed;
}
};
}
/*
0 1
0 2
-1 2
-2 3
*/
pii relative_position(pii origin, int orientation, pii tree) {
// Compute the raw relative coordinates
int dx = tree.first - origin.first;
int dy = tree.second - origin.second;
// Transform coordinates based on orientation
pii result;
switch (orientation) {
case 0: // forward (standard orientation)
result = {dx, dy};
break;
case 1: // backward (flip the y-axis)
result = {-dx, -dy};
break;
case 2: // left (swap x and y, negate x)
result = {-dy, dx};
break;
case 3: // right (swap x and y, negate y)
result = {dy, -dx};
break;
default:
cerr << "Invalid orientation!" << endl;
return {-1, -1}; // Error signal
}
return result;
}
pii compute_origin(pii tree, int orientation, pii direction_vector)
{
int dx = direction_vector.first;
int dy = direction_vector.second;
pii origin;
switch (orientation) {
case 0: // forward (standard)
origin = {tree.first - dx, tree.second - dy};
break;
case 1: // backward (reverse y)
origin = {tree.first + dx, tree.second + dy};
break;
case 2: // left (swap x and y, negate x)
origin = {tree.first + dy, tree.second - dx};
break;
case 3: // right (swap x and y, negate y)
origin = {tree.first - dy, tree.second + dx};
break;
default:
cerr << "Invalid orientation!" << endl;
assert(false);
}
return origin;
}
int solve()
{
int n, m, R;
if(!(cin>>n>>m>>R))return 1;
vector<pii> trees(n);
FOR(i,0,n)cin>>trees[i].x>>trees[i].y;
unordered_set<pii> tree_set{all(trees)};
unordered_set<pii> de;
de.reserve(5e6);
FOR(i,0,m)
{
int x,y;
cin>>x>>y;
de.insert({x,y});
}
auto check=[&](pii pos, int dir) -> bool{
int det_ctr=0;
for(auto [x,y]: trees)
{
auto tr=pii{x,y};
if(abs(x-pos.x)+abs(y-pos.y) <= R)
{
auto [xx,yy]=relative_position(pos, dir,tr);
if(de.find({xx,yy})==de.end())
return false;
++det_ctr;
}
}
return det_ctr==m;
};
int x0=de.begin()->x;
int y0=de.begin()->y;
//FOR(i,0,4) check({0,1},i);
//return 0;
set<array<int,3>> ob;
FOR(dir,0,4)
{
for(auto tr: trees)
{
auto [xx,yy]=compute_origin(tr,dir,{x0,y0});
//cout<<xx<<' '<<yy<<'\n';
if(tree_set.find({xx,yy})!=tree_set.end())
continue;
FOR(ori,0,4)
{
if(check({xx,yy}, ori))
{
ob.insert({xx,yy,ori});
}
}
}
}
if(sz(ob)==1)
{
cout<<(*ob.begin())[0]<<" "<<(*ob.begin())[1]<<'\n';
}
else if(sz(ob)==0)
{
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
cout << "__________________________" << endl;
#endif
}
#ifdef ONPC
cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 43364kb
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: 3ms
memory: 43368kb
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: 0
Accepted
time: 63ms
memory: 43600kb
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:
-9929 -9959
result:
ok single line: '-9929 -9959'
Test #4:
score: 0
Accepted
time: 22ms
memory: 43476kb
input:
4899 941 40 -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 -10000 -9955...
output:
Impossible
result:
ok single line: 'Impossible'
Test #5:
score: 0
Accepted
time: 19ms
memory: 43472kb
input:
4899 940 40 -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 -10000 -9955...
output:
Impossible
result:
ok single line: 'Impossible'
Test #6:
score: 0
Accepted
time: 2ms
memory: 43188kb
input:
3 3 1000 1 0 0 1 1 1 1 0 0 1 1 1
output:
0 0
result:
ok single line: '0 0'
Test #7:
score: 0
Accepted
time: 222ms
memory: 43472kb
input:
5000 2 1000 0 0 1000 1000 66740 84615 -16851 37613 31009 31589 -68041 -71122 21568 86889 53743 -31217 -73472 63365 9594 -12742 -25497 -5264 15942 13442 19537 -83361 93129 67319 -27565 73861 75273 -19266 -55048 -79726 -45975 -36987 -51309 35820 -99049 -10933 -45867 99815 -52121 99729 -89976 -15892 38...
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #8:
score: 0
Accepted
time: 224ms
memory: 43476kb
input:
5000 3 1000 0 0 1000 1000 1000 999 13954 9751 75888 -54632 10747 -12901 37707 -37988 -49564 26056 -30528 -9620 6227 -95560 -82768 85135 -15530 89254 -39739 -79664 -81590 -75580 91135 -20238 -52264 -66253 -41259 -90627 -7096 -35158 -67316 13384 79722 57595 -40566 99205 35854 -48598 -83531 -59472 -286...
output:
600 400
result:
ok single line: '600 400'
Test #9:
score: 0
Accepted
time: 2ms
memory: 43360kb
input:
4 3 100 1 1 2 2 2 1 3 3 0 1 0 2 -1 2
output:
Impossible
result:
ok single line: 'Impossible'
Test #10:
score: 0
Accepted
time: 3ms
memory: 43180kb
input:
3 3 100 1 1 2 1 3 1 0 1 0 2 0 3
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #11:
score: 0
Accepted
time: 4ms
memory: 43360kb
input:
4 3 2 1 1 2 2 2 1 3 3 0 1 0 2 -1 1
output:
2 0
result:
ok single line: '2 0'
Test #12:
score: 0
Accepted
time: 4ms
memory: 43236kb
input:
121 121 50 4 0 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 ...
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #13:
score: 0
Accepted
time: 2ms
memory: 43240kb
input:
120 120 50 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 2 4 ...
output:
5 5
result:
ok single line: '5 5'
Test #14:
score: 0
Accepted
time: 4ms
memory: 43244kb
input:
120 119 50 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 2 4 ...
output:
Impossible
result:
ok single line: 'Impossible'
Test #15:
score: 0
Accepted
time: 4ms
memory: 43368kb
input:
121 121 50 4 0 -10 10 8 0 0 -4 -6 10 -8 -8 10 6 2 2 -8 10 -4 -8 6 2 -2 -2 -10 -6 -4 10 4 2 -6 -6 10 -10 8 2 0 -2 -8 -6 2 4 -4 -6 6 4 -2 0 -10 -4 -6 -4 10 -8 8 4 0 0 -8 -4 -4 -4 6 6 -2 2 -10 -2 -6 -2 10 -6 2 -10 0 2 -8 -2 6 -10 -4 -2 4 -10 -2 4 -10 0 8 -10 -6 0 2 -8 -8 0 6 -8 10 8 -4 0 -10 2 8 -8 -6 ...
output:
Ambiguous
result:
ok single line: 'Ambiguous'
Test #16:
score: 0
Accepted
time: 80ms
memory: 43520kb
input:
2598 217 20 -28 50 -36 46 -16 24 -24 20 50 6 -44 -38 42 2 6 48 -42 8 -50 4 -30 -18 -38 -22 -20 26 -18 -44 -38 14 2 50 -46 10 -18 -8 22 28 -26 -12 14 24 -34 -16 -6 -34 -14 -38 26 -2 -22 -42 18 -6 -4 12 36 48 -12 8 8 -14 48 22 0 -18 18 30 -8 -22 20 -40 12 -44 30 4 4 -48 -8 14 12 -8 4 -12 44 24 24 -34 ...
output:
5 5
result:
ok single line: '5 5'