QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#140002 | #3168. Letter Wheels | Kirill22# | TL | 1ms | 3528kb | C++17 | 1.7kb | 2023-08-14 22:36:41 | 2023-08-14 22:36:45 |
Judging History
answer
#include "bits/stdc++.h"
using namespace std;
const int inf = (int) 1e9;
vector<int> z_function(const string& s) {
int n = s.size();
vector<int> z(n, 0);
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
z[i] = max(0, min(r - i, z[i - l]));
while (i + z[i] < n && s[z[i]] == s[z[i] + i]) z[i]++;
if (i + z[i] > r) {
l = i, r = i + z[i];
}
}
return z;
}
int solve2(string a, string b, string c) {
int ans = inf, n = (int) a.size();
for (int k = 0; k < n; k++) {
bool ok = true;
string need(n, 'a');
for (int i = 0; i < n; i++) {
if (a[i] == b[i]) {
ok = false;
}
if (a[i] != 'A' && b[i] != 'A') {
need[i] = 'A';
}
if (a[i] != 'B' && b[i] != 'B') {
need[i] = 'B';
}
if (a[i] != 'C' && b[i] != 'C') {
need[i] = 'C';
}
}
if (ok) {
string F = need + "#" + c + c;
auto z = z_function(F);
for (int j = n + 1; j <= 2 * n; j++) {
if (z[j] == n) {
ans = min(ans, k + j - (n + 1));
}
}
}
b.insert(b.begin(), b.back());
b.pop_back();
}
return ans;
}
int solve(string a, string b, string c) {
return min(solve2(a, b, c), solve2(a, c, b));
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string a, b, c;
cin >> a >> b >> c;
int ans = min({solve(a, b, c), solve(b, a, c), solve(c, a, b)});
cout << (ans == inf ? -1 : ans);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3528kb
input:
ABC ABC ABC
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3452kb
input:
ABBBAAAA BBBCCCBB CCCCAAAC
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3404kb
input:
AABB BBCC ACAC
output:
-1
result:
ok single line: '-1'
Test #4:
score: -100
Time Limit Exceeded
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...