QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227862 | #2932. Checker Slide | Thallium54# | AC ✓ | 29ms | 16632kb | C++20 | 3.1kb | 2023-10-28 01:12:57 | 2023-10-28 01:12:57 |
Judging History
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;
}
详细
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