QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#409429 | #3168. Letter Wheels | ucup-team1716# | TL | 1ms | 3640kb | C++14 | 2.1kb | 2024-05-12 03:35:50 | 2024-05-12 03:35:50 |
Judging History
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;
priority_queue<pair<int, pair<int, int> > > que;
que.push(mk(0, mk(0, 0)));
while (!que.empty()) {
pair<int, pair<int, int> > cur = que.top();
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
ABC ABC ABC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
ABBBAAAA BBBCCCBB CCCCAAAC
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3520kb
input:
AABB BBCC ACAC
output:
-1
result:
ok single line: '-1'
Test #4:
score: -100
Time Limit Exceeded
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...