QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#180969 | #3168. Letter Wheels | warwolf# | AC ✓ | 404ms | 251564kb | C++23 | 1.2kb | 2023-09-16 14:48:07 | 2023-09-16 14:48:08 |
Judging History
answer
#include <bits/stdc++.h>
#define maxn 5086
using namespace std;
int n;
int son[maxn * maxn][3], val[maxn * maxn];
int cnt;
int ans = 1e9;
char s[3][maxn];
void solve(){
for(int i = 1;i <= cnt;i++) memset(son[i], 0, sizeof(son[i])), val[i] = 1e9;
cnt = 1;
for(int i = 0;i < n;i++){
bool tag = false;
for(int j = 1;j <= n;j++){
int jj = j + i;
if(jj > n) jj -= n;
if(s[1][jj] == s[0][j]) tag = true;
}
if(tag) continue;
int now = 1;
for(int j = 1;j <= n;j++){
int jj = j + i;
if(jj > n) jj -= n;
int k = 3 - (s[1][jj] - 'A' + s[0][j] - 'A');
if(!son[now][k]) son[now][k] = ++cnt;
now = son[now][k];
}
val[now] = min(val[now], min(i, n - i));
}
for(int i = 0;i < n;i++){
int now = 1;
for(int j = 1;j <= n;j++){
int jj = j + i;
if(jj > n) jj -= n;
int k = s[2][jj] - 'A';
if(!son[now][k]) break;
now = son[now][k];
}
ans = min(ans, val[now] + min(i, n - i));
}
}
int main(){
memset(val, 0x3f, sizeof(val));
for(int i = 0;i < 3;i++) scanf("%s", s[i] + 1);
n = strlen(s[0] + 1);
solve();
for(int i = 1;i <= n;i++) swap(s[0][i], s[1][i]);
solve();
for(int i = 1;i <= n;i++) swap(s[0][i], s[2][i]);
solve();
printf("%d", ans == 1e9 ? -1 : ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 106916kb
input:
ABC ABC ABC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 104976kb
input:
ABBBAAAA BBBCCCBB CCCCAAAC
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 4ms
memory: 105248kb
input:
AABB BBCC ACAC
output:
-1
result:
ok single line: '-1'
Test #4:
score: 0
Accepted
time: 404ms
memory: 106212kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 146ms
memory: 105264kb
input:
ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...
output:
-1
result:
ok single line: '-1'
Test #6:
score: 0
Accepted
time: 59ms
memory: 105660kb
input:
ABBBCCACACBCBACCBBCCBACBBBABAABBCAACCABBBACABAACABBCAAACACABACAACACCBCABBABBCBBCCABBCCABCCACBCCCBABABAACAAACCCCBACCABBAACCAABCABBABAAABACBAABABCABAAACABAAACABBCBCACABACBBBBBBCCABBACAAAACBAAACABCABABBBABBAABACABABCCBCCBAAAABBCACACABBCABCAAAABABAAACBCCAAABCABBBAACBABBBACBBBCBCAABCCCCBBACCBABABBAAACAAB...
output:
911
result:
ok single line: '911'
Test #7:
score: 0
Accepted
time: 48ms
memory: 106272kb
input:
AACABBCACCCBABAACCBBACAAAACABCCCCCCAABBCACACBAACBBBCCBAABBCBAABCABBAABCABAACBBABBAAABBAACACBAACBBACAABCAACBCBCACBACAABCCBBACACCABCCCCCCCCACABBBCBCBBACACCBACCBCAACACAABABACCAACCCAABBBABCCCACBCBAACAACCCBAAABBCCCBBABBBBBABAACAACCABCAABCCABBAABCBACBAABBBACCBAABBCAAACACCCCCCCBBAAABBCBBCCACCAAACBABCCAABBB...
output:
465
result:
ok single line: '465'
Test #8:
score: 0
Accepted
time: 44ms
memory: 106908kb
input:
CBCBAABCCCABBACCBABCAABBCACBBBCABCCAABCCCABBCACAAAACACBCBCCCCBCBBCCCBACCAABABACCABCBCCBBCCAACABCCABBBBBABACCBCBABCACCCCCBBCBAABABBCACBCABBCAAAACBABCCACABABCBABABBCAABABCCAACABCBBBBCABCAAABCABCAACBBBBBCBBCAABCBACABACBBCAACBCBCCABBCABBACCBBABCBABBCCCBBCABABAACBBBACCCACBAAAACCCBACACAACBACABACCCCBACCCCA...
output:
861
result:
ok single line: '861'
Test #9:
score: 0
Accepted
time: 256ms
memory: 251500kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2612
result:
ok single line: '2612'
Test #10:
score: 0
Accepted
time: 258ms
memory: 251520kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2189
result:
ok single line: '2189'
Test #11:
score: 0
Accepted
time: 219ms
memory: 251476kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
1519
result:
ok single line: '1519'
Test #12:
score: 0
Accepted
time: 254ms
memory: 251508kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2546
result:
ok single line: '2546'
Test #13:
score: 0
Accepted
time: 259ms
memory: 251488kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2319
result:
ok single line: '2319'
Test #14:
score: 0
Accepted
time: 235ms
memory: 251424kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2505
result:
ok single line: '2505'
Test #15:
score: 0
Accepted
time: 246ms
memory: 251564kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2474
result:
ok single line: '2474'
Test #16:
score: 0
Accepted
time: 271ms
memory: 251520kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
2993
result:
ok single line: '2993'
Test #17:
score: 0
Accepted
time: 3ms
memory: 105620kb
input:
ACCCCBBB BBBACCCC BAAABAAA
output:
1
result:
ok single line: '1'
Test #18:
score: 0
Accepted
time: 7ms
memory: 106828kb
input:
CBBACBBAABAACCCBACCCBABAABBCABCABBACABBAAAAAACABCBCCACCABACBAAAAABBBABCCCBCBCACACACABBCBCACAAACCAABCCBCACABCBABBABBCBCCCACABCCBBCBCAACABBACCBCBCABABAAABACBBAAACACACBBACBBCACACACBCAAAABBCCBCBCCCBBBCBABCBBCACCCABBAACBACABAABBCABCBAACBCAABBBCACAAABAAABCBABACACBAAAABCAABACCABAAAACBCCBBCAAABABCABBAACCACC...
output:
183
result:
ok single line: '183'
Test #19:
score: 0
Accepted
time: 243ms
memory: 251472kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...
output:
1332
result:
ok single line: '1332'