QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#646029 | #4641. 聪明的打字员 | Geekmen | 100 ✓ | 1ms | 3932kb | C++14 | 2.4kb | 2024-10-16 20:58:17 | 2024-10-16 20:58:17 |
Judging History
answer
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> PII;
int s, t, n;
short dist[725][10][6];
signed main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> s >> t;
unordered_map<int, int> idx;
vector<int> st(725);
string tmp = to_string(s);
sort(tmp.begin(), tmp.end());
while (tmp.size() < 6) tmp.insert(tmp.begin(), '0');
do { idx[stoi(tmp)] = ++ n, st[n] = stoi(tmp); }while (next_permutation(tmp.begin(), tmp.end()));
memset(dist, -1, sizeof dist);
queue<array<int, 3>> q;
q.push({idx[s], 0, 0}), dist[idx[s]][0][0] = 0;
vector<array<int, 3>> avl;
while (q.size()) {
auto u = q.front();
q.pop(), avl.push_back(u);
string tmp = to_string(st[u[0]]);
while (tmp.size() < 6) tmp.insert(tmp.begin(), '0');
swap(tmp[0], tmp[u[2]]);
// swap0
int state = idx[stoi(tmp)], mask = u[1];
if (dist[state][mask][u[2]] == -1) dist[state][mask][u[2]] = dist[u[0]][u[1]][u[2]] + 1, q.push({state, mask, u[2]});
// swap1
swap(tmp[0], tmp[u[2]]), swap(tmp[5], tmp[u[2]]);
state = idx[stoi(tmp)], mask = u[1] + 5 * (u[1] < 5);
if (dist[state][mask][u[2]] == -1) dist[state][mask][u[2]] = dist[u[0]][u[1]][u[2]] + 1, q.push({state, mask, u[2]});
// right
state = u[0], mask = min(4 + 5 * (u[1] >= 5), u[1] + 1);
if (u[1] == 4) mask = 9;
if (dist[state][mask][min(5, u[2] + 1)] == -1) dist[state][mask][u[2] + 1] = dist[u[0]][u[1]][u[2]] + 1, q.push({state, mask, u[2] + 1});
// left
state = u[0], mask = u[1];
if (dist[state][mask][max(0, u[2] - 1)] == -1) dist[state][mask][max(0, u[2] - 1)] = dist[u[0]][u[1]][u[2]] + 1, q.push({state, mask, max(0, u[2] - 1)});
}
int res = 1E9;
for (auto v : avl) {
string tmp = to_string(st[v[0]]), tt = to_string(t);
while (tmp.size() < 6) tmp.insert(tmp.begin(), '0');
while (tt.size() < 6) tt.insert(tt.begin(), '0');
int cost = dist[v[0]][v[1]][v[2]];
for (int i = 0; i <= v[1] % 5; i ++) cost += abs(tt[i] - tmp[i]);
int lst = v[1] % 5;
for (int i = v[1] % 5 + 1; i < 5; i ++)
if (abs(tt[i] - tmp[i]))
cost += abs(tt[i] - tmp[i]) + i - lst, lst = i;
if (v[1] >= 5) cost += abs(tt[5] - tmp[5]);
else if (abs(tt[5] - tmp[5])) cost += abs(tt[5] - tmp[5]) + 5 - lst;
res = min(res, cost);
}
cout << res << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Pretests
Final Tests
Test #1:
score: 10
Accepted
time: 1ms
memory: 3832kb
input:
123456 654321
output:
11
result:
ok single line: '11'
Test #2:
score: 10
Accepted
time: 1ms
memory: 3728kb
input:
000000 000000
output:
0
result:
ok single line: '0'
Test #3:
score: 10
Accepted
time: 1ms
memory: 3836kb
input:
123456 499199
output:
26
result:
ok single line: '26'
Test #4:
score: 10
Accepted
time: 0ms
memory: 3832kb
input:
180273 321931
output:
15
result:
ok single line: '15'
Test #5:
score: 10
Accepted
time: 0ms
memory: 3700kb
input:
000000 999999
output:
59
result:
ok single line: '59'
Test #6:
score: 10
Accepted
time: 1ms
memory: 3724kb
input:
120099 554433
output:
25
result:
ok single line: '25'
Test #7:
score: 10
Accepted
time: 0ms
memory: 3752kb
input:
001988 543345
output:
26
result:
ok single line: '26'
Test #8:
score: 10
Accepted
time: 1ms
memory: 3780kb
input:
908172 022345
output:
21
result:
ok single line: '21'
Test #9:
score: 10
Accepted
time: 0ms
memory: 3720kb
input:
999999 123456
output:
38
result:
ok single line: '38'
Test #10:
score: 10
Accepted
time: 1ms
memory: 3932kb
input:
051423 980980
output:
26
result:
ok single line: '26'