QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227862#2932. Checker SlideThallium54#AC ✓29ms16632kbC++203.1kb2023-10-28 01:12:572023-10-28 01:12:57

Judging History

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

  • [2023-10-28 01:12:57]
  • 评测
  • 测评结果:AC
  • 用时:29ms
  • 内存:16632kb
  • [2023-10-28 01:12:57]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>

 
const int N = 2e5 + 100;
const int inf = 1e9;
const ll mod =  998244353;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    using st = array<array<int, 2>, 4>;
    st s, t;
    for (auto& v : s) for (auto& x : v) cin >> x;
    for (auto& v : t) for (auto& x : v) cin >> x;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end());

    auto encode = [](st a) {
        sort(a.begin(), a.end());
        int res = 0;
        for (auto [x, y] : a) {
            res = res * 36 + x * 6 + y;
        }
        return res;
    };

    const int N = 36 * 36 * 36 * 36;
    vector<int> pre(N, -1), dis(N, 0);

    const int ss = encode(s);
    pre[encode(s)] = encode(s);
    queue<st> q;
    q.push(s);

    vector<array<int, 2>> dir{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    vector has(6, vector(6, 0));
    while (!q.empty()) {
        auto u = q.front();
        // for (auto [x, y] : u) {
        //     cout << x << ' ' << y << ' ';
        // }
        // cout << endl;
        q.pop();

        int cs = encode(u);
        for (auto [x, y] : u) {
            has[x][y] = 1;
        }


        for (auto& [x, y] : u) {
            for (auto [dx, dy] : dir) {
                int ox = x, oy = y;
                has[x][y] = 0;
                int lx = x, ly = y;
                while (1) {
                    x += dx, y += dy;
                    if (x < 0 || x >= 6 || y < 0 || y >= 6 || has[x][y]) break;
                    lx = x, ly = y;
                }
                x = lx, y = ly;
                int ns = encode(u);
                if (pre[ns] == -1) {
                    pre[ns] = cs;
                    dis[ns] = dis[cs] + 1;
                    q.push(u);
                }
                x = ox, y = oy;
                has[x][y] = 1;
            }
        }

        for (auto [x, y] : u) {
            has[x][y] = 0;
        }
    }

    int fs = encode(t);
    assert(pre[fs] != -1);

    cout << dis[fs] << '\n';

    vector<array<int, 4>> ans;

    auto decode = [](int s) {
        st res;
        for (auto& [x, y] : res) {
            int r = s % 36;
            y = r % 6;
            x = r / 6;
            s /= 36;
        }
        return res;
    };

    int cs = fs;
    while (cs != ss) {
        auto cur = decode(cs);
        auto pr = decode(pre[cs]);
        set<array<int, 2>> ss(pr.begin(), pr.end());
        array<int, 2> rem;
        for (auto x : cur) {
            if (ss.count(x)) {
                ss.erase(x);
            } else {
                rem = x;
            }
        }
        assert(ss.size() == 1);

        auto [xx, yy] = *ss.begin();
        ans.push_back({xx, yy, rem[0], rem[1]});

        cs = pre[cs];
    }

    reverse(ans.begin(), ans.end());
    for (auto [a, b, c, d] : ans) {
        cout << a << ' ' << b << ' ' << c << ' ' << d << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 25ms
memory: 16596kb

input:

5 5 5 0 0 5 0 0
2 2 2 1 1 2 1 1

output:

12
0 5 0 1
5 0 5 4
0 0 5 0
5 4 5 1
5 5 5 2
5 1 1 1
5 0 5 1
5 1 2 1
1 1 1 5
0 1 1 1
1 5 1 2
5 2 2 2

result:

ok correct plan

Test #2:

score: 0
Accepted
time: 24ms
memory: 16428kb

input:

3 2 2 1 1 0 0 3
4 3 3 5 1 3 0 4

output:

18
1 0 1 5
1 5 5 5
2 1 2 5
5 5 3 5
3 5 3 3
0 3 2 3
2 5 2 4
2 4 5 4
3 2 5 2
5 2 5 3
3 3 4 3
5 4 0 4
5 3 5 0
5 0 0 0
0 0 0 3
0 3 1 3
2 3 3 3
3 3 3 5

result:

ok correct plan

Test #3:

score: 0
Accepted
time: 28ms
memory: 16532kb

input:

5 5 3 4 2 0 0 2
3 4 3 0 0 2 0 1

output:

4
5 5 5 0
5 0 3 0
2 0 0 0
0 0 0 1

result:

ok correct plan

Test #4:

score: 0
Accepted
time: 27ms
memory: 16624kb

input:

3 5 2 1 1 5 0 3
2 2 1 3 1 2 0 1

output:

6
3 5 2 5
2 5 2 2
2 1 0 1
0 3 0 2
0 2 1 2
1 5 1 3

result:

ok correct plan

Test #5:

score: 0
Accepted
time: 23ms
memory: 16560kb

input:

2 2 1 5 0 3 0 1
2 2 1 4 0 3 0 1

output:

8
0 3 0 2
0 2 1 2
1 2 1 4
1 5 0 5
0 5 0 2
0 2 1 2
1 2 1 3
1 3 0 3

result:

ok correct plan

Test #6:

score: 0
Accepted
time: 29ms
memory: 16632kb

input:

5 0 4 5 3 0 1 0
4 4 4 0 3 5 1 0

output:

6
5 0 4 0
4 0 4 4
4 5 5 5
5 5 5 0
5 0 4 0
3 0 3 5

result:

ok correct plan

Test #7:

score: 0
Accepted
time: 27ms
memory: 16556kb

input:

5 3 4 3 1 4 1 2
3 4 3 2 2 2 0 1

output:

18
1 2 1 3
1 3 3 3
1 4 0 4
4 3 4 0
5 3 4 3
4 3 4 1
4 0 0 0
0 4 0 1
0 1 3 1
0 0 0 5
4 1 4 5
0 5 3 5
3 5 3 4
3 3 3 2
3 1 0 1
4 5 0 5
0 5 0 2
0 2 2 2

result:

ok correct plan

Test #8:

score: 0
Accepted
time: 29ms
memory: 16552kb

input:

1 5 1 4 1 3 1 0
5 3 5 2 3 4 3 1

output:

20
1 0 5 0
1 3 5 3
1 5 5 5
5 3 5 4
5 4 2 4
5 0 5 4
5 4 3 4
2 4 2 0
1 4 2 4
2 4 2 1
2 0 5 0
5 5 5 1
5 0 0 0
0 0 0 5
0 5 5 5
5 5 5 2
5 1 3 1
2 1 2 5
2 5 5 5
5 5 5 3

result:

ok correct plan

Test #9:

score: 0
Accepted
time: 24ms
memory: 16488kb

input:

3 4 3 3 3 1 2 3
5 1 1 4 1 1 0 2

output:

16
2 3 2 5
2 5 5 5
3 1 0 1
3 3 5 3
5 5 5 4
5 3 5 0
3 4 0 4
5 4 1 4
0 4 0 2
0 2 5 2
5 0 5 1
5 1 1 1
0 1 0 0
0 0 5 0
5 0 5 1
5 2 0 2

result:

ok correct plan

Test #10:

score: 0
Accepted
time: 28ms
memory: 16468kb

input:

3 2 2 0 0 2 0 1
2 1 1 0 0 2 0 1

output:

5
0 2 2 2
2 0 2 1
2 2 0 2
3 2 1 2
1 2 1 0

result:

ok correct plan

Test #11:

score: 0
Accepted
time: 23ms
memory: 16420kb

input:

3 2 3 1 2 3 0 4
3 2 1 2 0 3 0 2

output:

6
3 1 0 1
0 4 0 2
0 2 2 2
2 3 0 3
0 1 0 2
2 2 1 2

result:

ok correct plan

Test #12:

score: 0
Accepted
time: 21ms
memory: 16560kb

input:

3 1 2 3 1 2 0 2
5 0 2 1 1 2 1 1

output:

6
0 2 0 0
2 3 2 0
0 0 1 0
1 0 1 1
2 0 5 0
3 1 2 1

result:

ok correct plan

Test #13:

score: 0
Accepted
time: 23ms
memory: 16496kb

input:

3 3 3 1 2 3 0 4
2 0 1 5 1 0 0 3

output:

7
0 4 0 0
3 1 3 0
3 0 1 0
2 3 2 0
1 0 1 5
0 0 1 0
3 3 0 3

result:

ok correct plan

Test #14:

score: 0
Accepted
time: 24ms
memory: 16512kb

input:

3 1 2 2 1 3 0 1
4 4 3 2 2 3 0 0

output:

18
0 1 0 5
1 3 5 3
3 1 3 5
0 5 2 5
2 5 2 3
5 3 3 3
2 2 5 2
5 2 5 5
3 5 3 4
3 3 5 3
5 5 5 4
5 4 4 4
3 4 3 0
5 3 3 3
3 0 3 2
3 3 3 5
3 5 0 5
0 5 0 0

result:

ok correct plan

Test #15:

score: 0
Accepted
time: 24ms
memory: 16472kb

input:

5 3 3 1 2 5 2 4
3 4 0 4 0 2 0 1

output:

7
2 5 5 5
5 5 5 4
5 4 3 4
2 4 0 4
3 1 0 1
5 3 0 3
0 3 0 2

result:

ok correct plan