QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #621384 | #3420. Jingle Balls | wangqingxian | AC ✓ | 0ms | 8020kb | C++20 | 2.2kb | 2024-10-08 14:06:46 | 2024-10-08 14:06:48 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=3e5+10,inf=1e9,mod=1e4+7;
vector<int>dp[N];
int genshin;
int cnt=0;
int ls[N],rs[N],stk[N],top,tot=0,sum[N];
bool lf[N];
void build(string s){
for(int i=1;i<=cnt;++i){
dp[i].clear();
ls[i]=rs[i]=0;
sum[i]=0;lf[i]=0;
stk[i]=0;
}
top=0;tot=0;cnt=0;
for(int i=0;i<s.size();++i){
if(s[i]=='(')stk[++top]=++cnt;
else if(s[i]=='B'){
lf[cnt]=1;
++tot;
}
else{
--top;
if(ls[stk[top]])rs[stk[top]]=stk[top+1];
else ls[stk[top]]=stk[top+1];
}
}
// dp[0].clear();
// dp[0].resize(tot);
// for(int i=0;i<=tot;++i)dp[0][i]=inf;
}
void dfs(int t,int siz){
if(!t)return;
dp[t].resize(siz+1);
for(int i=0;i<=siz;++i)dp[t][i]=inf;
if(!ls[t]&&!rs[t]){
dp[t][lf[t]]=0;
dp[t][1-lf[t]]=1;
sum[t]=1;
return;
}
dfs(ls[t],siz/2+1);
if(!rs[t]){
dp[t][1]=dp[ls[t]][1];
dp[t][0]=dp[ls[t]][0];
return;
}
dfs(rs[t],siz/2+1);
sum[t]=sum[ls[t]]+sum[rs[t]];
for(int i=0;i<=min(siz,sum[t]);++i){
if(dp[ls[t]].size()<=i/2||dp[rs[t]].size()<=i/2)continue;
if(!(i&1))
dp[t][i]=min(dp[t][i],dp[ls[t]][i/2]+dp[rs[t]][i/2]);
else{
if(dp[rs[t]].size()>i/2+1)
dp[t][i]=min(dp[t][i],dp[ls[t]][i/2]+dp[rs[t]][i/2+1]);
if(dp[ls[t]].size()>i/2+1)
dp[t][i]=min(dp[t][i],dp[ls[t]][i/2+1]+dp[rs[t]][i/2]);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
string s;
while(cin>>s){
build(s);
dfs(1,tot);
// for(int i=1;i<=cnt;++i){
// cout<<i<<endl;
// for(int j=0;j<dp[i].size();++j)cout<<dp[i][j]<<" ";
// cout<<endl;
// }
if(dp[1][tot]!=inf)cout<<dp[1][tot]/2<<endl;
else cout<<"impossible"<<endl;
}
// // cerr<<fixed<<setprecision(3)<<(double)clock()/CLOCKS_PER_SEC<<endl;
return 0;
}
/*
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7608kb
input:
((B)()) ((((B)(B))((B)()))(B)) (()(((B)(B))(B)))
output:
0 impossible 1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 8020kb
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