QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #136657 | #236. Balanced Sequence | Delay_for_five_minutes# | 100 ✓ | 37ms | 11316kb | C++20 | 2.1kb | 2023-08-09 09:47:17 | 2023-08-09 09:47:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
string s[100005];
int sum[100005] , mn[100005];
vector<pair<int,int> > pos , neg;
bool check(int x)
{
int s = 0;
for(int i = 0;i < pos.size();i++) {
if(s + pos[i].first < -x) return 0;
s += pos[i].second ;
}
//printf("HERE %d\n" , s);
int t = 0 , mn = 0;
for(int i = 0;i < neg.size();i++) {
mn = min(mn , t + neg[i].first);
t += neg[i].second;
}
mn = min(mn , t);
int delta = -x - mn;
// printf("here %d %d , %d\n",t,mn,delta);
t += delta ;
return (t <= s);
}
void solve()
{
cin >> n; pos.clear() ; neg.clear() ;
int l = 0 , r = 0 , sm = 0, len = 0;
for(int i = 1;i <= n;i++) {
cin >> s[i]; r += s[i].size(); len += s[i].size();
sum[i] = 0;
mn[i] = 0;
for(int j = 0;j < s[i].size();j++) {
if(s[i][j] == '(') sum[i]++;
else sum[i]--;
mn[i] = min(mn[i] , sum[i]);
}
sm += sum[i];
if(sum[i] >= 0) {
pos.push_back(pair<int,int>{mn[i] , sum[i]});
}
else {
sum[i] = 0; mn[i] = 0;
for(int j = s[i].size() - 1;j >= 0;j--) {
if(s[i][j] == '(') sum[i]--;
else sum[i]++;
mn[i] = min(mn[i] , sum[i]);
}
neg.push_back(pair<int,int>{mn[i] , sum[i]});
}
}
sort(pos.begin() , pos.end()); reverse(pos.begin() , pos.end());
sort(neg.begin() ,neg.end()); reverse(neg.begin() , neg.end());
//for(auto [x,y] : pos) printf("pos %d %d\n",x,y);
// for(auto [x,y] : neg) printf("neg %d %d\n",x,y);
//check(0) ; return ;
while(l < r) {
int md = (l + r >> 1);
if(check(md)) r = md;
else l = md + 1;
}
// cout << len <<' ' << sm <<' ' << l << '\n';
cout << len - (abs(sm + l) + l) << '\n';
}
int main()
{
// freopen("in.txt","r",stdin);
ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0);
int t;cin >> t;
while(t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 37ms
memory: 11316kb
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