QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#710943 | #2932. Checker Slide | BackToSquare1 | AC ✓ | 89ms | 10336kb | C++20 | 5.0kb | 2024-11-04 23:22:31 | 2024-11-04 23:22:31 |
Judging History
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