QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#710943#2932. Checker SlideBackToSquare1AC ✓89ms10336kbC++205.0kb2024-11-04 23:22:312024-11-04 23:22:31

Judging History

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

  • [2024-11-04 23:22:31]
  • 评测
  • 测评结果:AC
  • 用时:89ms
  • 内存:10336kb
  • [2024-11-04 23:22:31]
  • 提交

answer

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
 
typedef pair<ll, ll> pl;
typedef pair<ld,ld> pd;
typedef vector<ll> vl;
// typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
 
#define G(x) ll x; cin >> x;
#define F(i, l, r) for (ll i = l; i < (r); ++i)
#define all(a) begin(a), end(a)
#define K first
#define V second
#define OK(i,j) i >= 0 && i < n && j >= 0 && j < m
 
#define NN 2505
#define MM 5005
#define MOD 1000000007

set<ll> visited;
queue<ll> q;
map<ll,ll> depths;
map<ll,ll> par;

void solve() {
    ll start[8], finish[8];
    for(ll i=0;i<8;i++) cin >> start[i];
    for(ll i=0;i<8;i++) cin >> finish[i];

    ll cur = 0;
    for(ll i=0;i<4;i++) cur += (1ll << (6*start[2*i] + start[2*i+1ll]));

    visited.insert(cur);
    q.push(cur);
    depths[cur] = 0;
    par[cur] = 0;
    ll ct = 0;
    ll x = cur;

    while(!q.empty()) {
        cur = q.front();
        q.pop();
        ll c = depths[cur];
        ct++;

        ll idx = 0;
        while(idx < 36) {
            // if(x == cur) cout << "HI1\n";
            if(cur&(1ll << idx)) {
                cur ^= (1ll << idx);

                ll i = idx/6;
                ll j = idx%6;

                if(ct == 1) {
                    // cout << "HI2 " << (cur^(1ll << idx)) << ' ' << idx << '\n';
                }

                ll d = 0;
                while(i+d < 6 && !(cur&(1ll << 6*(i+d) + j))) d++;
                d--;
                if(visited.count(cur ^ (1ll << 6*(i+d) + j)) == 0) {
                    q.push(cur ^ (1ll << 6*(i+d) + j));
                    visited.insert(cur ^ (1ll << 6*(i+d) + j));
                    depths[cur ^ (1ll << 6*(i+d) + j)] = c+1;
                    par[cur ^ (1ll << 6*(i+d) + j)] = (cur ^ (1ll << idx));

                    // if(ct == 1) cout << 0 << ' ' << i << ' ' << j << ' ' << d << '\n';
                }

                d = 0;
                while(i-d >= 0 && !(cur&(1ll << 6*(i-d) + j))) d++;
                d--;
                if(visited.count(cur ^ (1ll << 6*(i-d) + j)) == 0) {
                    q.push(cur ^ (1ll << 6*(i-d) + j));
                    visited.insert(cur ^ (1ll << 6*(i-d) + j));
                    depths[cur ^ (1ll << 6*(i-d) + j)] = c+1;
                    par[cur ^ (1ll << 6*(i-d) + j)] = (cur ^ (1ll << idx));

                    // if(ct == 1) cout << 1 << ' ' << i << ' ' << j << ' ' << d << '\n';
                }

                d = 0;
                while(j+d < 6 && !(cur&(1ll << 6*i + j + d))) d++;
                d--;
                if(visited.count(cur ^ (1ll << 6*i + j + d)) == 0) {
                    q.push(cur ^ (1ll << 6*i + j + d));
                    visited.insert(cur ^ (1ll << 6*i + j + d));
                    depths[cur ^ (1ll << 6*i + j + d)] = c+1;
                    par[cur ^ (1ll << 6*i + j + d)] = (cur ^ (1ll << idx));

                    // if(ct == 1) cout << 2 << ' ' << i << ' ' << j << ' ' << d << '\n';
                }

                d = 0;
                while(j-d >= 0 && !(cur&(1ll << 6*i + j - d))) d++;
                d--;
                if(visited.count(cur ^ (1ll << 6*i + j - d)) == 0) {
                    q.push(cur ^ (1ll << 6*i + j - d));
                    visited.insert(cur ^ (1ll << 6*i + j - d));
                    depths[cur ^ (1ll << 6*i + j - d)] = c+1;
                    par[cur ^ (1ll << 6*i + j - d)] = (cur ^ (1ll << idx));

                    // if(ct == 1) cout << 3 << ' ' << i << ' ' << j << ' ' << d << '\n';
                }

                cur ^= (1ll << idx);
            }
            idx++;
        }
    }

    ll stop = 0;
    for(ll i=0;i<4;i++) stop += (1ll << (6*finish[2*i] + finish[2*i+1]));

    cout << depths[stop] << '\n';
    if(depths[stop] == 0) return;
    ll len = depths[stop];
    ll ans[len][4];
    ll k = 0;

    while(par[stop] != 0) {
        // cout << stop << ' ' << par[stop] << '\n';
        ll i1=0, j1=0, i2=0, j2=0;
        ll idx = 0;
        while(idx < 36) {
            if(((stop&(1ll << idx)) == 0) && ((par[stop]&(1ll << idx)) != 0)) {
                i1 = idx/6;
                j1 = idx%6;
            }
            else if(((stop&(1ll << idx)) != 0) && ((par[stop]&(1ll << idx)) == 0)) {
                i2 = idx/6;
                j2 = idx%6;
            }
            idx++;
        }

        stop = par[stop];
        ans[k][0] = i1;
        ans[k][1] = j1;
        ans[k][2] = i2;
        ans[k][3] = j2;
        k++;
        
    }

    reverse(ans,ans+len);

    for(ll i=0;i<len;i++) {
        for(ll j=0;j<4;j++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }

    // cout << ct << '\n';

}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cout << fixed << setprecision(10);

    solve();

    return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 87ms
memory: 9848kb

input:

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

output:

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

result:

ok correct plan

Test #2:

score: 0
Accepted
time: 87ms
memory: 9616kb

input:

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

output:

18
1 0 5 0 
2 1 2 5 
5 0 5 5 
5 5 3 5 
2 5 0 5 
0 5 0 4 
0 3 5 3 
3 5 3 3 
3 2 0 2 
0 2 0 3 
0 3 2 3 
3 3 4 3 
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: 83ms
memory: 9656kb

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: 86ms
memory: 9612kb

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: 79ms
memory: 9680kb

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: 77ms
memory: 9656kb

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: 88ms
memory: 9808kb

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: 89ms
memory: 10336kb

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: 85ms
memory: 9824kb

input:

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

output:

16
2 3 0 3 
0 3 0 5 
3 1 0 1 
3 3 0 3 
0 3 0 4 
0 5 5 5 
3 4 1 4 
0 4 0 2 
5 5 5 0 
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: 80ms
memory: 9848kb

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: 87ms
memory: 9544kb

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: 86ms
memory: 9816kb

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: 83ms
memory: 9656kb

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 
1 0 1 5 
2 3 2 0 
0 0 1 0 
3 3 0 3 

result:

ok correct plan

Test #14:

score: 0
Accepted
time: 83ms
memory: 9644kb

input:

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

output:

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

result:

ok correct plan

Test #15:

score: 0
Accepted
time: 86ms
memory: 9680kb

input:

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

output:

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

result:

ok correct plan