QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#409431#3168. Letter Wheelsucup-team1716#AC ✓782ms101884kbC++142.1kb2024-05-12 03:36:422024-05-12 03:36:43

Judging History

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

  • [2024-05-12 03:36:43]
  • 评测
  • 测评结果:AC
  • 用时:782ms
  • 内存:101884kb
  • [2024-05-12 03:36:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mk make_pair

const int MAXN = 5000;
const int INF = 1e9;

int n;

string s[3];

int ok1[MAXN + 5], ok2[MAXN + 5], ok3[MAXN + 5];

int dis[MAXN + 5][MAXN + 5];
const int dx[6] = {1, -1, 0, 0, 1, -1}, dy[6] = {0, 0, 1, -1, 1, -1};

int main() {
	cin >> s[0] >> s[1] >> s[2];
	
	n = s[0].length();
	
	for (int i = 0; i < n; ++i) {
		// consider only s[0] and s[1], is it valid to rotate s[1] i times?
		ok1[i] = true;
		for (int j = 0; j < n; ++j) {
			if (s[0][j] == s[1][(j + i) % n]) {
				ok1[i] = false;
				break;
			}
		}
	}
	
	for (int i = 0; i < n; ++i) {
		// consider only s[0] and s[2], is it valid to rotate s[2] i times?
		ok2[i] = true;
		for (int j = 0; j < n; ++j) {
			if (s[0][j] == s[2][(j + i) % n]) {
				ok2[i] = false;
				break;
			}
		}
	}
	
	for (int i = 0; i < n; ++i) {
		// consider only s[1] and s[2], is it valid to rotate s[2] i times?
		ok3[i] = true;
		for (int j = 0; j < n; ++j) {
			if (s[1][j] == s[2][(j + i) % n]) {
				ok3[i] = false;
				break;
			}
		}
	}
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			dis[i][j] = INF;
		}
	}
	
	dis[0][0] = 0;
	
	queue<pair<int, pair<int, int> > > que;
	que.push(mk(0, mk(0, 0)));
	
	while (!que.empty()) {
		pair<int, pair<int, int> > cur = que.front();
		que.pop();
		int x = cur.se.fi;
		int y = cur.se.se;
		if (-cur.fi != dis[x][y]) {
			continue;
		}
		
		for (int i = 0; i < 6; ++i) {
			int xx = (x + dx[i] + n) % n, yy = (y + dy[i] + n) % n;
			if (dis[xx][yy] > dis[x][y] + 1) {
				dis[xx][yy] = dis[x][y] + 1;
				que.push(mk(-dis[xx][yy], mk(xx, yy)));
			}
		}
	}
	
	int ans = INF;
	for (int i = 0; i < n; ++i) { // rotate s[1] i times
		for (int j = 0; j < n; ++j) { // rotate s[2] j times
			int k = ((j >= i) ? j - i : j - i + n); // relative to s[1], s[2] is like rotated k times
			if (ok1[i] && ok2[j] && ok3[k]) {
				// cout << i << " " << j << endl;
				ans = min(ans, dis[i][j]);
			}
		}
	}
	
	if (ans == INF)
		ans = -1;
	cout << ans << endl;
	
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3660kb

input:

ABC
ABC
ABC

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3868kb

input:

ABBBAAAA
BBBCCCBB
CCCCAAAC

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

AABB
BBCC
ACAC

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 782ms
memory: 101644kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 676ms
memory: 101652kb

input:

ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 633ms
memory: 101696kb

input:

ABBBCCACACBCBACCBBCCBACBBBABAABBCAACCABBBACABAACABBCAAACACABACAACACCBCABBABBCBBCCABBCCABCCACBCCCBABABAACAAACCCCBACCABBAACCAABCABBABAAABACBAABABCABAAACABAAACABBCBCACABACBBBBBBCCABBACAAAACBAAACABCABABBBABBAABACABABCCBCCBAAAABBCACACABBCABCAAAABABAAACBCCAAABCABBBAACBABBBACBBBCBCAABCCCCBBACCBABABBAAACAAB...

output:

911

result:

ok single line: '911'

Test #7:

score: 0
Accepted
time: 627ms
memory: 101548kb

input:

AACABBCACCCBABAACCBBACAAAACABCCCCCCAABBCACACBAACBBBCCBAABBCBAABCABBAABCABAACBBABBAAABBAACACBAACBBACAABCAACBCBCACBACAABCCBBACACCABCCCCCCCCACABBBCBCBBACACCBACCBCAACACAABABACCAACCCAABBBABCCCACBCBAACAACCCBAAABBCCCBBABBBBBABAACAACCABCAABCCABBAABCBACBAABBBACCBAABBCAAACACCCCCCCBBAAABBCBBCCACCAAACBABCCAABBB...

output:

465

result:

ok single line: '465'

Test #8:

score: 0
Accepted
time: 625ms
memory: 101540kb

input:

CBCBAABCCCABBACCBABCAABBCACBBBCABCCAABCCCABBCACAAAACACBCBCCCCBCBBCCCBACCAABABACCABCBCCBBCCAACABCCABBBBBABACCBCBABCACCCCCBBCBAABABBCACBCABBCAAAACBABCCACABABCBABABBCAABABCCAACABCBBBBCABCAAABCABCAACBBBBBCBBCAABCBACABACBBCAACBCBCCABBCABBACCBBABCBABBCCCBBCABABAACBBBACCCACBAAAACCCBACACAACBACABACCCCBACCCCA...

output:

861

result:

ok single line: '861'

Test #9:

score: 0
Accepted
time: 725ms
memory: 101540kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2612

result:

ok single line: '2612'

Test #10:

score: 0
Accepted
time: 706ms
memory: 101584kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2189

result:

ok single line: '2189'

Test #11:

score: 0
Accepted
time: 687ms
memory: 101848kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1519

result:

ok single line: '1519'

Test #12:

score: 0
Accepted
time: 714ms
memory: 101884kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2546

result:

ok single line: '2546'

Test #13:

score: 0
Accepted
time: 720ms
memory: 101688kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2319

result:

ok single line: '2319'

Test #14:

score: 0
Accepted
time: 700ms
memory: 101532kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2505

result:

ok single line: '2505'

Test #15:

score: 0
Accepted
time: 707ms
memory: 101516kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2474

result:

ok single line: '2474'

Test #16:

score: 0
Accepted
time: 713ms
memory: 101684kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2993

result:

ok single line: '2993'

Test #17:

score: 0
Accepted
time: 0ms
memory: 3640kb

input:

ACCCCBBB
BBBACCCC
BAAABAAA

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 7ms
memory: 16280kb

input:

CBBACBBAABAACCCBACCCBABAABBCABCABBACABBAAAAAACABCBCCACCABACBAAAAABBBABCCCBCBCACACACABBCBCACAAACCAABCCBCACABCBABBABBCBCCCACABCCBBCBCAACABBACCBCBCABABAAABACBBAAACACACBBACBBCACACACBCAAAABBCCBCBCCCBBBCBABCBBCACCCABBAACBACABAABBCABCBAACBCAABBBCACAAABAAABCBABACACBAAAABCAABACCABAAAACBCCBBCAAABABCABBAACCACC...

output:

183

result:

ok single line: '183'

Test #19:

score: 0
Accepted
time: 702ms
memory: 101652kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1332

result:

ok single line: '1332'