QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#115333 | #2359. The Five Bishops | ckiseki | TL | 0ms | 0kb | C++20 | 4.1kb | 2023-06-25 19:43:09 | 2023-06-25 19:43:10 |
Judging History
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;
});
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
Time Limit Exceeded
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 3 7 2 7 2 7 2 6 2 6 1 7 1 7 2 6 2 6 1 7 1 7 2 7 2 7 3 7 3 7 4 6 4 6 4 7 4 7 5 8 5 8 4 9 4 9 3 10 3 10 4 9 4 9 3 10 3 10 4 10 4 10 5 11 5 11 5 12 5 12 6 12 6 12 5 12 5 12 5 13 5 13 6 12 6 12 5 13 5 13 5 14 5 14 6 15 6 1...
output:
0 0 0 0 1 1 21481795 -21481793 1 2 -14364011 14364014 1 4 69092630 -69092625 1 5 -28087177 28087183 21481795 -21481793 21481796 -21481792 -14364011 14364014 -14364010 14364015 21481796 -21481792 21481797 -21481791 -14364010 14364015 -14364009 14364016 -28087177 28087183 -28087178 28087182 69092630 -...