QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#731539 | #8554. Bot Friends | nhuang685 | WA | 64ms | 3656kb | C++23 | 2.2kb | 2024-11-10 07:42:42 | 2024-11-10 07:42:42 |
Judging History
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'