QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#115333#2359. The Five BishopsckisekiTL 0ms0kbC++204.1kb2023-06-25 19:43:092023-06-25 19:43:10

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-25 19:43:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-06-25 19:43: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;
    });
    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;
}

详细

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 -...

result: