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 |
|---|---|---|---|---|---|---|---|---|---|
| #136926 | #236. Balanced Sequence | Rd_rainydays | 100 ✓ | 34ms | 4700kb | C++20 | 1.1kb | 2023-08-09 14:06:00 | 2023-08-09 14:06:02 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 200005
using namespace std;
int T;
int n;
char s[123123];
int a[N],b[N];
struct zero{
int nl,nr;
friend bool operator<(zero a,zero b){return a.nr-a.nl>b.nr-b.nl;}
}lib[N];
bool cmp(zero a,zero b){return (a.nl^b.nl)?a.nl<b.nl:a.nr>b.nr;}
bool cmp2(zero a,zero b){return (a.nr^b.nr)?a.nr>b.nr:a.nl<b.nl;}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
int ans=0;
for(int i=1;i<=n;i++)lib[i].nl=lib[i].nr=0;
for(int i=1;i<=n;i++){
scanf("%s",s+1);
int len=strlen(s+1);
int cnt=0;
for(int p=1;p<=len;p++){
if(s[p]=='(')cnt++;
else {
if(cnt>0)cnt--,ans+=2;
else lib[i].nl++;
}
}
lib[i].nr=cnt;
}
sort(lib+1,lib+n+1);
int pos=n;
for(int i=1;i<=n;i++)if(lib[i].nr-lib[i].nl<0){pos=i-1;break;}
if(pos>=1)sort(lib+1,lib+pos+1,cmp);
if(pos<n)sort(lib+pos+1,lib+n+1,cmp2);
int cnt=0;
for(int i=1;i<=n;i++){
if(cnt>lib[i].nl)cnt-=lib[i].nl,ans+=2*lib[i].nl;
else ans+=2*cnt,cnt=0;
cnt+=lib[i].nr;
}
printf("%d\n",ans);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 34ms
memory: 4700kb
input:
482 2 ()())())())()(()))))(())()())))))))))))((()()()))(()()((((((())))(())()) ((())(((()(())())())()))))(( 2 (()(()))))())))))()(()))(())( ())(()()(()(()))(((()))))))())))))))))(()())()((()))()()))(()(()(((())) 1 ))())(())(())(()()()((())())(())))()(()(()(())()((()()()))()((()(()(((()))))(((((()(()...
output:
80 80 88 86 92 90 88 86 92 98 84 96 80 88 96 92 92 90 96 82 92 80 82 84 88 94 88 80 92 82 88 88 88 90 82 88 96 78 96 98 94 98 68 78 82 90 90 92 90 80 78 90 78 84 94 94 84 90 84 92 96 96 82 92 90 90 88 86 94 94 88 94 84 86 96 86 82 90 98 82 78 94 88 86 80 88 96 86 84 86 92 84 84 90 92 82 86 94 84 94 ...
result:
ok 482 lines