QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#877184#7696. Forest for the TreesLaVuna47AC ✓224ms43600kbC++204.8kb2025-01-31 20:11:322025-01-31 20:11:32

Judging History

This is the latest submission verdict.

  • [2025-01-31 20:11:32]
  • Judged
  • Verdict: AC
  • Time: 224ms
  • Memory: 43600kb
  • [2025-01-31 20:11:32]
  • Submitted

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'