QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#140002#3168. Letter WheelsKirill22#TL 1ms3528kbC++171.7kb2023-08-14 22:36:412023-08-14 22:36:45

Judging History

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

  • [2023-08-14 22:36:45]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3528kb
  • [2023-08-14 22:36:41]
  • 提交

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...

output:


result: