QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#283070 | #1194. Parehtneses Editor | NYCU_template# | WA | 1ms | 6816kb | C++20 | 1.3kb | 2023-12-13 19:14:30 | 2023-12-13 19:14:30 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int N = 2e5 + 5;
ll dp[N], n, match[N];
string s;
stack<pair<char, ll>> st1, st2;
int main() {
cin >> s;
n = (int)s.size();
memset(match, -1, sizeof(match));
ll inval_cnt = 0, ans = 0;
for(int i = 0; i < n; i++) {
char c = s[i];
if(c == '-') {
char cc = st2.top().first;
int ii = st2.top().second;
if(cc == ')' && match[ii] != -1) {
ans -= dp[ii];
st1.emplace('(', match[ii]);
} else {
st1.pop();
}
st2.pop();
} else {
if(c == '(') st1.emplace(c, i);
else {
if(st1.empty() || st1.top().first == ')') {
st1.emplace(c, i);
} else {
int l_id = st1.top().second;
match[i] = l_id;
if(l_id) dp[i] = dp[l_id - 1] + 1;
else dp[i] = 1;
ans += dp[i];
st1.pop();
// cerr << "match[" << i << "] = " << match[i] << endl;
}
}
st2.emplace(c, i);
}
cout << ans << "\n";
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5356kb
input:
(()())---)
output:
0 0 1 1 3 4 3 1 1 2
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 6816kb
input:
()--()()----)(()()))
output:
0 1 0 0 0 1 1 3 1 1 0 0 0 0 0 1 1 3 4 4
result:
ok 20 numbers
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 6160kb
input:
))(((-)(()((---(-)(-())-(()()(-)--(())))--()((())-)(()(())((-))))(-(((()((()()()()))-(())((((--))-())-)(-(--))))((((-)(-(-)((((()--(---)(-))()(-)(()()-(())()(()()((()()))))(()(()(-(--)-()((()(((()-))-)(()-()()-(-((-)(-)(((()-)))))-())()-(()((()(-)()))((-))())))()()()(-(-(())-()(()-)-))((()))((--(-()...
output:
0 0 0 0 0 0 1 1 1 2 2 2 2 2 1 1 1 2 2 2 2 3 5 3 3 3 4 4 6 6 6 7 6 4 4 4 5 6 8 9 8 6 6 7 7 7 7 8 9 8 9 9 9 10 10 10 11 13 13 13 13 16 18 20 22 22 22 22 22 22 22 23 23 23 23 24 24 26 26 29 29 33 34 36 34 34 34 35 36 36 36 36 36 36 36 37 39 37 37 38 40 38 40 40 40 40 40 38 40 42 43 44 44 44 44 44 44 45...
result:
wrong answer 22nd numbers differ - expected: '4', found: '3'