QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#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

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2022-07-09 23:13:16]
评测

测评结果：AC
用时：33ms
内存：9064kb

查看

[2022-07-09 23:13:14]
提交

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;
}

源文件, 语言: C++

详细

Test #1:

score: 100

Accepted

time: 33ms

memory: 9064kb

input:

482
2
()())())())()(()))))(())()())))))))))))((()()()))(()()((((((())))(())())
((())(((()(())())())()))))((
2
(()(()))))())))))()(()))(())(
())(()()(()(()))(((()))))))())))))))))(()())()((()))()()))(()(()(((()))
1
))())(())(())(()()()((())())(())))()(()(()(())()((()()()))()((()(()(((()))))(((((()(()...

output:

result:

ok 482 lines