QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#646029#4641. 聪明的打字员Geekmen100 ✓1ms3932kbC++142.4kb2024-10-16 20:58:172024-10-16 20:58:17

Judging History

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

  • [2024-10-16 20:58:17]
  • 评测
  • 测评结果:100
  • 用时:1ms
  • 内存:3932kb
  • [2024-10-16 20:58:17]
  • 提交

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'