QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#731539#8554. Bot Friendsnhuang685WA 64ms3656kbC++232.2kb2024-11-10 07:42:422024-11-10 07:42:42

Judging History

This is the latest submission verdict.

  • [2024-11-10 07:42:42]
  • Judged
  • Verdict: WA
  • Time: 64ms
  • Memory: 3656kb
  • [2024-11-10 07:42:42]
  • Submitted

answer

/**
 * @author n685
 * @brief
 * @date 2024-11-09 18:10:18
 *
 *
 */
#include "bits/stdc++.h"

#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif

namespace rs = std::ranges;
namespace rv = std::views;

template <class T> constexpr T INF = T{};
template <std::floating_point T> constexpr T INF<T> = std::numeric_limits<T>::infinity();
template <> constexpr int INF<int> = 0x3f3f3f3f;                 // 1061109567
template <> constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399

template <class T> bool ckmin(T& a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T> bool ckmax(T& a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

void solve() {
  std::string s;
  std::cin >> s;
  int n = static_cast<int>(s.size());
  using Arr = std::vector<std::array<int, 2>>;
  const Arr id = std::vector<std::array<int, 2>>(n + 1, std::array<int, 2>{INF<int>, INF<int>});
  std::array<Arr, 2> dp{};
  dp[0] = id;
  dp[0][0][0] = 0;
  for (int i = 0; i < n; ++i) {
    dp[1] = id;
    for (int j = 0; j <= n; ++j) {
      if (s[i] != '>') {
        ckmin(dp[1][j][0], dp[0][j][0] + 1);
        ckmin(dp[1][j][0], dp[0][j][1] + 1);
        if (j > 0) {
          ckmin(dp[1][j - 1][0], dp[0][j][0]);
          ckmin(dp[1][j - 1][0], dp[0][j][1] + 1);
        }
      }
      if (s[i] != '<') {
        if (j > 0) {
          ckmin(dp[1][j][1], dp[0][j][0]);
        } else {
          ckmin(dp[1][j + 1][1], dp[0][j][0]);
        }
        if (j < n) {
          ckmin(dp[1][j + 1][1], dp[0][j][1]);
        }
      }
    }
    dp[0].swap(dp[1]);
  }
  int ans = n;
  for (int j = 0; j <= n; ++j) {
    ans = std::min({ans, dp[0][j][0] - (j > 0) + j, dp[0][j][1] + j});
  }
  std::cout << n - ans << '\n';
}

int main() {
#ifndef LOCAL
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
#endif

  int t;
  std::cin >> t;
  for (int i = 0; i < t; ++i) {
    dbg(i + 1);
    solve();
    bar();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

10
?>?
>?<
??<?
?><?<
??????
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>

output:

2
2
3
4
5
8
7
8
5
6

result:

ok 10 numbers

Test #2:

score: -100
Wrong Answer
time: 64ms
memory: 3656kb

input:

100000
>?<?<>?<?<
?><???><><
??>>><><??
<>>?>>?>?>
<?<>>??<?>
>><>><<<<<
>?>?>?<<>>
?><?<<?<><
???><>?>?>
<??>?<<><?
??>><?<>>>
<><><?<>>?
?>>?>???><
?<?><?<<>?
>>><?<??><
><><<>?>?<
>?><>><<<?
>??>?><?<>
?????<><?>
<><<?<<>?<
><?>>?>?>?
?><><<<>>?
?<>?<>?<<<
<><<<<<>>>
?>?>?><<>>
<>?<>><>?<
<<<?<>>...

output:

8
7
8
5
6
7
6
6
6
7
6
5
8
6
8
7
8
7
7
6
6
7
7
2
6
6
3
9
6
5
5
7
5
8
7
6
8
7
7
6
6
7
4
2
7
5
8
7
8
5
6
5
7
8
8
8
8
7
5
5
7
7
6
8
7
5
8
6
6
8
7
7
6
8
5
7
6
6
5
5
7
7
5
3
8
6
5
7
5
7
6
7
7
8
3
8
8
7
8
7
7
4
8
8
7
5
8
6
7
7
8
7
5
7
8
5
7
6
5
8
8
7
7
8
6
7
8
6
6
8
7
8
7
6
5
5
7
8
6
8
6
7
5
7
4
6
6
7
7
7
...

result:

wrong answer 6th numbers differ - expected: '8', found: '7'