QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164136#4275. Escape SequenceswsyearWA 2ms5712kbC++171.8kb2023-09-04 20:14:122023-09-04 20:14:13

Judging History

This is the latest submission verdict.

  • [2023-09-04 20:14:13]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 5712kb
  • [2023-09-04 20:14:12]
  • Submitted

answer

#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

const int N = 200010;

int n, m, a[N], b[N], fail[N], kmp[N];
char s[N], t[N];

bool check() {
  // 判断 b 是否在 a 中出现
  fail[1] = 0;
  rep (i, 2, m) {
    int j = fail[i - 1];
    while (j && b[i] != b[j + 1]) j = fail[j];
    fail[i] = j + (b[i] == b[j + 1]);
  }
  rep (i, 1, n) {
    int j = kmp[i - 1];
    while (j && a[i] != b[j + 1]) j = fail[j];
    kmp[i] = j + (a[i] == b[j + 1]);
  }
  rep (i, 1, n) if (kmp[i] == m) return 1;
  return 0;
}

int main() {
  cin.tie(nullptr) -> ios::sync_with_stdio(false);
  cin >> (s + 1) >> (t + 1);
  n = strlen(s + 1), m = strlen(t + 1);
  rep (i, 1, n) a[i] = s[i] - 'a';
  rep (i, 1, m) b[i] = t[i] - 'a';
  int ans = -1, cnt = 0;
  while (n && m) {
    if (check()) { ans = cnt; break; }
    cnt++;
    bool fa = 1, fb = 1;
    rep (i, 1, m) {
      if (i & 1) fa &= (b[i] == 0);
      else fb &= (b[i] == 0);
    }
    if (m == 1) break;
    if (fa) {
      if (m & 1) n--;
      int mm = 0;
      rep (i, 1, m) if (!(i & 1)) b[++mm] = b[i];
      m = mm;
    } else if (fb) {
      if (!(m & 1)) n--;
      int mm = 0;
      rep (i, 1, m) if (i & 1) b[++mm] = b[i];
      m = mm;
    } else {
      break;
    }
  }
  cout << ans << '\n';
}

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5712kb

input:

b
ab

output:

1

result:

ok 1 number(s): "1"

Test #2:

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

input:

ababa
bab

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5648kb

input:

a
b

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

abbb
baa

output:

2

result:

ok 1 number(s): "2"

Test #5:

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

input:

abaabb
abaab

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 5712kb

input:

aaab
aaba

output:

-1

result:

ok 1 number(s): "-1"

Test #7:

score: 0
Accepted
time: 0ms
memory: 5684kb

input:

bbbabbbbbbbabbabbbbaaaaaaaabbabaaabababaaababbbabaabbabbaababbabbbbbbbbbabbabbabbbbabaababaaaaa
bbaabbaabbbaaaaabbaaaaaabbabbaababababbbbabaabbbabbaaaabababaabbbababbabbbbaabbbbbbb

output:

-1

result:

ok 1 number(s): "-1"

Test #8:

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

input:

abbbbbabbbbabbbbaabbbaabaaabab
abababbabaaabbaaaaabbbabbaabbaaabaabababbb

output:

-1

result:

ok 1 number(s): "-1"

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3676kb

input:

bbaabaabaaab
aaaaaaaaaaaaaaa

output:

3

result:

wrong answer 1st numbers differ - expected: '2', found: '3'