QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#876551#7696. Forest for the TreesWeaRD276WA 1058ms3840kbC++202.9kb2025-01-30 23:50:052025-01-30 23:50:09

Judging History

This is the latest submission verdict.

  • [2025-01-30 23:50:09]
  • Judged
  • Verdict: WA
  • Time: 1058ms
  • Memory: 3840kb
  • [2025-01-30 23:50:05]
  • Submitted

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;
	
	assert(n >= m);
	set<pii> tr;
	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;
		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.count(cur);
		}
		//cerr << "==================================\n";
		return ok;
	};
	
	//1 1
	//2 2
	//2 1
	//3 3
	
	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;
			}
			//cerr << cur.x << ' ' << cur.y << '\n';
			if (check(cur, d))
				poses.pb({cur.x, cur.y, d});
				
			//FOR (j, 0, 4)
				//if (check(cur, j))
					//poses.pb({cur.x, cur.y, j});
		}
	}
	//FOR (i, 0, 4)
		//cout << check({0, 1}, i) << '\n';
	
	//cerr << sz(poses) << '\n';
	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: 0ms
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: 1ms
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
Wrong Answer
time: 1058ms
memory: 3840kb

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:

Ambiguous

result:

wrong answer 1st lines differ - expected: '-9929 -9959', found: 'Ambiguous'