QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106759#3168. Letter Wheelsmarsxiang5902#AC ✓277ms4052kbC++171.8kb2023-05-19 04:46:462023-05-19 04:46:48

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-19 04:46:48]
  • 评测
  • 测评结果:AC
  • 用时:277ms
  • 内存:4052kb
  • [2023-05-19 04:46:46]
  • 提交

answer

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

using ll = long long;
const int MN = 5e3+5, MOD = 1e9+7, HN = 1;

int N, ar[3][MN], need[MN]; ll pw[HN][MN], pc[HN][3][MN], needH[HN]; string ss[3];

ll getHsh(int h, int *a) {
  ll ret = 0;
  for (int i = 0; i < N; i++)
    ret += a[i] * pw[h][i];
  return ret %MOD;
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  for (int s = 0; s < 3; s++)
    cin >> ss[s];
  N = ss[0].size();
  for (int s = 0; s < 3; s++)
    for (int i = 0; i < N; i++)
      ar[s][i] = ss[s][i] - 'A' + 1;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()*0+3);
  uniform_int_distribution<int> dist(5, 20);
  for (int h = 0; h < HN; h++) {
    pw[h][0] = 1;
    pw[h][1] = dist(rng);
    for (int i = 2; i < N; i++)
      pw[h][i] = pw[h][i-1] * pw[h][1] %MOD;
    for (int s = 0; s < 3; s++) {
      ll pvH = getHsh(h, ar[s]);
      for (int i = 0; i < N; i++) {
        pc[h][s][i] = pvH;
        pvH = ((pvH + MOD - ar[s][N-1-i] * pw[h][N-1]%MOD) * pw[h][1] + ar[s][N-1-i]) %MOD;
      }
    }
  }
  int ans = 1e9;
  for (int s = 0; s < 3; s++) {
    int s1 = (s+1) %3, s2 = (s+2) %3;
    for (int r1 = 0; r1 < N; r1++) {
      bool b = 1;
      for (int i = 0, i1 = (N-r1)%N; i < N; i++, i1 = (i1 == N-1 ? 0 : i1+1)) {
        b &= ar[s][i] != ar[s1][i1];
        need[i] = 6 - ar[s][i] - ar[s1][i1];
      }
      if (!b) continue;
      for (int h = 0; h < HN; h++)
        needH[h] = getHsh(h, need);
      for (int r2 = 0; r2 < N; r2++) {
        bool b1 = 1;
        for (int h = 0; h < HN; h++)
          b1 &= pc[h][s2][r2] == needH[h];
        if (b1) ans = min(ans, min(r1, N-r1) + min(r2, N-r2));
      }
    }
  }
  printf("%d\n", ans == 1e9 ? -1 : ans);

  return 0;
}

详细

Test #1:

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

input:

ABC
ABC
ABC

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3608kb

input:

ABBBAAAA
BBBCCCBB
CCCCAAAC

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3756kb

input:

AABB
BBCC
ACAC

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 277ms
memory: 3796kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 117ms
memory: 3776kb

input:

ABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABABAB...

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 93ms
memory: 3824kb

input:

ABBBCCACACBCBACCBBCCBACBBBABAABBCAACCABBBACABAACABBCAAACACABACAACACCBCABBABBCBBCCABBCCABCCACBCCCBABABAACAAACCCCBACCABBAACCAABCABBABAAABACBAABABCABAAACABAAACABBCBCACABACBBBBBBCCABBACAAAACBAAACABCABABBBABBAABACABABCCBCCBAAAABBCACACABBCABCAAAABABAAACBCCAAABCABBBAACBABBBACBBBCBCAABCCCCBBACCBABABBAAACAAB...

output:

911

result:

ok single line: '911'

Test #7:

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

input:

AACABBCACCCBABAACCBBACAAAACABCCCCCCAABBCACACBAACBBBCCBAABBCBAABCABBAABCABAACBBABBAAABBAACACBAACBBACAABCAACBCBCACBACAABCCBBACACCABCCCCCCCCACABBBCBCBBACACCBACCBCAACACAABABACCAACCCAABBBABCCCACBCBAACAACCCBAAABBCCCBBABBBBBABAACAACCABCAABCCABBAABCBACBAABBBACCBAABBCAAACACCCCCCCBBAAABBCBBCCACCAAACBABCCAABBB...

output:

465

result:

ok single line: '465'

Test #8:

score: 0
Accepted
time: 99ms
memory: 3864kb

input:

CBCBAABCCCABBACCBABCAABBCACBBBCABCCAABCCCABBCACAAAACACBCBCCCCBCBBCCCBACCAABABACCABCBCCBBCCAACABCCABBBBBABACCBCBABCACCCCCBBCBAABABBCACBCABBCAAAACBABCCACABABCBABABBCAABABCCAACABCBBBBCABCAAABCABCAACBBBBBCBBCAABCBACABACBBCAACBCBCCABBCABBACCBBABCBABBCCCBBCABABAACBBBACCCACBAAAACCCBACACAACBACABACCCCBACCCCA...

output:

861

result:

ok single line: '861'

Test #9:

score: 0
Accepted
time: 129ms
memory: 3928kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2612

result:

ok single line: '2612'

Test #10:

score: 0
Accepted
time: 120ms
memory: 4052kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2189

result:

ok single line: '2189'

Test #11:

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

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1519

result:

ok single line: '1519'

Test #12:

score: 0
Accepted
time: 123ms
memory: 3824kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2546

result:

ok single line: '2546'

Test #13:

score: 0
Accepted
time: 124ms
memory: 3820kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2319

result:

ok single line: '2319'

Test #14:

score: 0
Accepted
time: 124ms
memory: 3792kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2505

result:

ok single line: '2505'

Test #15:

score: 0
Accepted
time: 127ms
memory: 3992kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2474

result:

ok single line: '2474'

Test #16:

score: 0
Accepted
time: 129ms
memory: 3800kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

2993

result:

ok single line: '2993'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

ACCCCBBB
BBBACCCC
BAAABAAA

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 4ms
memory: 3608kb

input:

CBBACBBAABAACCCBACCCBABAABBCABCABBACABBAAAAAACABCBCCACCABACBAAAAABBBABCCCBCBCACACACABBCBCACAAACCAABCCBCACABCBABBABBCBCCCACABCCBBCBCAACABBACCBCBCABABAAABACBBAAACACACBBACBBCACACACBCAAAABBCCBCBCCCBBBCBABCBBCACCCABBAACBACABAABBCABCBAACBCAABBBCACAAABAAABCBABACACBAAAABCAABACCABAAAACBCCBBCAAABABCABBAACCACC...

output:

183

result:

ok single line: '183'

Test #19:

score: 0
Accepted
time: 128ms
memory: 3796kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...

output:

1332

result:

ok single line: '1332'