QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #301233 | #7894. Many Many Heads | ship2077 | WA | 0ms | 3764kb | C++14 | 752b | 2024-01-09 16:20:13 | 2024-01-09 16:20:13 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
mt19937_64 mt(time(NULL));
constexpr int M=1e5+5;string s;
int n,tp,a[M],stk[M];
ull Hash,val[2],base[M];
void solve(){
cin>>s;n=s.length();s=" "+s;
val[0]=mt();val[1]=mt();Hash=0;
for (int i=1;i<=n;i++) base[i]=mt();
for (int i=1;i<=n;i++) a[i]=s[i]=='('||s[i]==')';
unordered_map<ull,bool>mp[2];mp[a[1]][0]=1;
for (int i=1;i<n;i++){
if (tp&&a[stk[tp]]==a[i])
Hash-=base[tp--]*val[a[i]];
else Hash+=base[++tp]*val[a[i]],stk[tp]=a[i];
if (mp[a[i+1]][Hash]) return puts("No"),void();
mp[a[i+1]][Hash]=1;
}
puts("Yes");
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;cin>>T;while (T--) solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
6 )) ((() [()] ()[()]() ([()]) ([])([])
output:
Yes No Yes No Yes No
result:
ok 6 token(s): yes count is 3, no count is 3
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3692kb
input:
2 (([([[([ ]]))])]])]
output:
Yes Yes
result:
wrong answer expected NO, found YES [2nd token]