QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #834220 | #3420. Jingle Balls | SGColin# | AC ✓ | 1ms | 4036kb | C++20 | 2.0kb | 2024-12-27 13:53:30 | 2024-12-27 13:53:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tii;
typedef vector<int> vi;
#define pb push_back
#define eb emplace_back
#define all(s) (s).begin(), (s).end()
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
constexpr int N = 2007;
string s;
int ptr, n, ls[N], rs[N], sz[N], dep[N], num[N][2];
void dfs(int u) {
++ptr;
ls[u] = rs[u] = sz[u] = 0;
if (s[ptr + 1] == 'B') {sz[u] = 1; ptr += 2; return;}
if (s[ptr + 1] == ')') {sz[u] = 0; ptr += 1; return;}
ls[u] = ++n; dep[n] = dep[u] + 1; dfs(n);
rs[u] = ++n; dep[n] = dep[u] + 1; dfs(n);
sz[u] = sz[ls[u]] + sz[rs[u]];
++ptr;
}
constexpr int inf = 1000'000'000;
int f[N][2];
void dp(int u) {
if (!ls[u]) {
f[u][0] = (num[dep[u]][0] > 1 ? inf : 0);
f[u][1] = (num[dep[u]][1] > 1 ? inf : 0);
return;
}
dp(ls[u]);
dp(rs[u]);
f[u][0] = f[u][1] = inf;
rep(i, 0, 1) {
int dlt = num[dep[u]][i] - sz[u];
rep(j, 0, 1) if (f[ls[u]][j] < inf) {
rep(k, 0, 1) if (f[rs[u]][k] < inf && num[dep[ls[u]]][j] + num[dep[rs[u]]][k] == num[dep[u]][i]) {
int dltl = num[dep[ls[u]]][j] - sz[ls[u]];
int dltr = num[dep[rs[u]]][k] - sz[rs[u]];
int cst;
if ((dltl < 0) == (dltr < 0)) cst = 0;
else cst = min(abs(dltl), abs(dltr));
f[u][i] = min(f[u][i], f[ls[u]][j] + f[rs[u]][k] + cst);
}
}
}
}
inline void work() {
ptr = -1; n = 1; dfs(1);
num[0][0] = num[0][1] = sz[1];
rep(i, 1, n) {
num[i][0] = num[i - 1][0] / 2;
num[i][1] = (num[i - 1][1] + 1) / 2;
}
dp(1);
int ans = min(f[1][0], f[1][1]);
if (ans >= inf) puts("impossible");
else printf("%d\n", ans);
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
while (cin >> s) work();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3928kb
input:
((B)()) ((((B)(B))((B)()))(B)) (()(((B)(B))(B)))
output:
0 impossible 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 4036kb
input:
(()()) (()(B)) ((B)(B)) (((B)(B))(B)) (()((B)(B))) ((()((B)(B)))(B)) ((()())((B)(B))) (((B)((B)(B)))(B)) (()(((B)((B)(B)))())) (((B)(B))(()((B)(B)))) ((B)(((B)((B)()))(B))) ((((((B)(B))(()(((B)(B))())))(((B)((B)(B)))((()())(()()))))((((()(B))((B)()))(((((B)(B))((B)(()(B))))())(B)))((((B)())())((B)(B...
output:
0 0 0 0 1 1 1 impossible 2 1 impossible 6 56 2 1 impossible 2 2 2 0 1 1 impossible 0 2 impossible 2 1 impossible 25 18 11 0 8 1 impossible 6 7 impossible 2 1 impossible 250 231 222 0 8 1 impossible 15 20 impossible 2 1 impossible 6 3 2 0 8 1 impossible 2 1 impossible 2 1 impossible 62 53 54 0 8 1 im...
result:
ok 78 lines