QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #39450 | #236. Balanced Sequence | afhi | AC ✓ | 33ms | 9064kb | C++ | 2.5kb | 2022-07-09 23:13:14 | 2022-07-09 23:13:16 |
Judging History
answer
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <string>
#include <cmath>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <set>
#include <map>
#include <random>
#include <climits>
#define SZ(x) (int) x.size()
using ll = long long;
template<typename T> using V = std::vector<T>;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
using std::cerr;
using std::cin;
using std::cout;
using str = std::string;
std::array<int,3> gao(const str& s) {
std::array<int,3> ret{0};
int n = SZ(s);
int left_bracket = 0;
for (int i = 0;i < n;i++) {
if (s[i] == '(') {
left_bracket += 1;
} else if (left_bracket != 0) {
left_bracket -= 1;
ret[0] += 2;
} else {
ret[2] += 1;
}
}
ret[1] = left_bracket;
return ret;
}
using pii = std::pair<int,int>;
void solve() {
int n;
std::cin>>n;
V<str> s(n);
for (int i = 0;i < n;i++) {
std::cin>>s[i];
}
int ans = 0;
V<pii> v_v[2];
for (int i = 0;i < n;i++) {
auto c = gao(s[i]);
ans += c[0];
if (c[1] - c[2] >= 0) {
v_v[0].emplace_back(c[1],c[2]);
} else {
v_v[1].emplace_back(c[2],c[1]);
}
}
std::sort(v_v[0].begin(),v_v[0].end(),[] (pii a,pii b) {
return a.second < b.second;
});
int acc = 0;
for (auto [a,b] : v_v[0]) {
int t = std::min(acc,b);
acc -= t;
ans += 2 * t;
acc += a;
}
int left = acc;
acc = 0;
std::sort(v_v[1].begin(),v_v[1].end(),[] (pii a,pii b) {
return a.second < b.second;
});
for (auto [a,b] : v_v[1]) {
int t = std::min(acc,b);
acc -= t;
ans += 2 * t;
acc += a;
}
int right = acc;
ans += std::min(left,right) * 2;
std::cout<<ans<<'\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cin.exceptions(std::cin.failbit);
std::cout<<std::fixed<<std::setprecision(10);
#ifdef DEBUG
freopen("input.txt","r",stdin);
#endif
int t;
std::cin>>t;
while (t--) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 33ms
memory: 9064kb
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