QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116292#2359. The Five BishopsckisekiRE 0ms0kbC++203.5kb2023-06-28 13:01:092023-06-28 13:07:24

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-28 13:07:24]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-06-28 13:01:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

void solve() {
	array<pair<int, int>, 5> b;
	pair<int, int> king;
	for (auto &[x, y] : b)
		scanf("%d%d", &x, &y);
	scanf("%d%d", &king.first, &king.second);

	auto move_to = [&](int x1, int y1, int x2, int y2) {
		printf("%d %d %d %d\n", x1, y1, x2, y2);
		fflush(stdout);
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		if (x1 == 0 and y1 == 0 and x2 == 0 and y2 == 0)
			return true;
		king = {x2, y2};
		return false;
	};

	vector<int> c[2] = {};
	for (int i = 0; i < 5; ++i) {
		auto [x, y] = b[i];
		c[(x + y) & 1].push_back(i);
	}
	if (c[0].size() < 2 or c[1].size() < 2) {
		puts("0 0 0 0");
		fflush(stdout);
		return;
	}
	if (c[0].size() == 3) c[0].pop_back();
	if (c[1].size() == 3) c[1].pop_back();

	vector<pair<int, int>> cur;
	for (int i : c[0]) cur.push_back(b[i]);
	for (int i : c[1]) cur.push_back(b[i]);

	sort(cur.begin(), cur.end());
	int o = king.first + king.second;
	vector<int> tar = {o - 11, o - 10, o + 10, o + 11};
	bool gogo = false;
	do {
		do {
			auto tmp = cur;
			bool valid = true;
			for (int i = 0; i < 4; ++i) {
				auto [x, y] = tmp[i];
				valid &= ((x + y) % 2 == tar[i] % 2);
			}
			if (not valid) continue;

			for (int i = 0; i < 4; ++i) {
				auto [x, y] = tmp[i];
				int s = (x + y);
				int k = tar[i];
				int d = (k - s) / 2;
				
				for (int j = 0; j < 4; ++j) {
					if (i == j) continue;
					auto [xx, yy] = tmp[j];
					if (x - y == xx - yy) {
						if (x <= xx and xx <= x + d)
							valid = false;
						if (x + d <= xx and xx <= d)
							valid = false;
					}
				}
				if (not valid) break;
				tmp[i] = {x + d, y + d};
			}
			if (not valid) continue;

			for (int i = 0; i < 4; ++i) {
				auto [x, y] = cur[i];
				auto [nx, ny] = tmp[i];
				if (move_to(x, y, nx, ny)) return;
				cur[i] = tmp[i];
			}
			gogo = true;
			break;
		} while (next_permutation(tar.begin(), tar.end()));
		if (gogo) break;
	} while (next_permutation(cur.begin(), cur.end()));

	mt19937 rnd(7122);
	uniform_int_distribution<int> rng(-100'000'000, 100'000'000);
	for (int i = 0; i < 4; ++i) {
		auto [x, y] = cur[i];
		int nx = rng(rnd);
		int ny = x + y - nx;
		if (move_to(x, y, nx, ny))
			return;
		cur[i] = {nx, ny};
	}

	sort(cur.begin(), cur.end(), [](pair<int, int> lhs, pair<int, int> rhs) {
		return lhs.first + lhs.second < rhs.first + rhs.second;
	});
	assert (cur[1].first + cur[1].second < king.first + king.second);
	assert (king.first + king.second < cur[2].first + cur[2].second);
	while (true) {
		if (cur[0].first + cur[0].second + 2 != king.first + king.second) {
			if (move_to(cur[0].first, cur[0].second, cur[0].first + 1, cur[0].second + 1)) {
				return;
			}
			++cur[0].first, ++cur[0].second;
			swap(cur[0], cur[1]);
			continue;
		}
		if (cur[3].first + cur[3].second - 2 != king.first + king.second) {
			if (move_to(cur[3].first, cur[3].second, cur[3].first - 1, cur[3].second - 1)) {
				return;
			}
			--cur[3].first, --cur[3].second;
			swap(cur[3], cur[2]);
			continue;
		}
		break;
	}
	int x1 = king.first, y1 = king.second + 2;
	if (move_to(cur[3].first, cur[3].second, x1, y1)) {
		return;
	}
	cur[3] = {x1, y1};
	int x2 = king.first, y2 = king.second - 2;
	if (move_to(cur[0].first, cur[0].second, x2, y2)) {
		return;
	}
	cur[0] = {x2, y2};
	int x3 = king.first, y3 = king.second - 2;
	assert(move_to(cur[0].first, cur[0].second, x3, y3));
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Dangerous Syscalls

input:

4
1 1 2 2 3 3 4 4 5 5 7 5
1 1 1 2 1 4 1 5 2 2 3 5
3 5 4 6
4 6 3 5
3 5 4 6
4 6 3 7

output:

0 0 0 0
1 1 21481795 -21481793
1 2 -14364011 14364014
1 4 69092630 -69092625
1 5 -28087177 28087183

result: