QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#682206	#7894. Many Many Heads	mvec	WA	14ms	3844kb	C++14	1.9kb	2024-10-27 14:24:49	2024-10-27 14:24:49

Judging History

This is the latest submission verdict.

[2024-10-27 14:24:49]
Judged

Verdict: WA
Time: 14ms
Memory: 3844kb

Show

[2024-10-27 14:24:49]
Submitted

answer

#include <iostream>
#include <string>
#include <bitset>
#include <stack>
#include <deque>

using namespace std;

struct seq
{
    int l, r, t;
};

string s;
bitset<1000010> bin_s;

bool solve(int l, int r)
{
    if (l >= r)
        return true;
    deque<seq> seqs;
    stack<char> ord;
    int index = 0;
    for (int i = l; i <= r; i++)
    {
        if (bin_s[i])
        {
            if (ord.size() && ord.top() == '[')
                ord.pop();
            else
                ord.push('[');

            if (ord.empty())
            {
                seqs.emplace_back();
                seqs.back().r = i;
                seqs.back().t = 1;
            }
        }
        else
        {
            if (ord.size() && ord.top() == '(')
                ord.pop();
            else
                ord.push('(');

            if (ord.empty())
            {
                seqs.emplace_back();
                seqs.back().r = i;
                seqs.back().t = 0;
            }
        }
    }
    if (seqs.empty())
        return true;
    seqs.front().l = 0;
    auto p1 = seqs.begin(), p2 = p1 + 1;
    while (p2 != seqs.end())
    {
        p2->l = p1->r + 1;
        p1++, p2++;
    }

    int cnts[2] = {0, 0};
    for (auto &p : seqs)
        cnts[p.t]++;

    if (cnts[0] > 1 || cnts[1] > 1)
        return false;

    for (auto &x : seqs)
        if (!solve(x.l + 1, x.r - 1))
            return false;

    return true;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> s;
        n = s.size();
        for (int i = 0; i < n; i++)
        {
            if (s[i] == '(' || s[i] == ')')
                bin_s[i] = 0;
            else
                bin_s[i] = 1;
        }

        if (solve(0, n - 1))
            cout << "Yes\n";
        else
            cout << "No\n";
    }

    return 0;
}

源文件, 语言: C++14

详细

Test #1:

score: 100

Accepted

time: 1ms

memory: 3844kb

input:

6
))
((()
[()]
()[()]()
([()])
([])([])

output:

Yes
No
Yes
No
Yes
No

result:

ok 6 token(s): yes count is 3, no count is 3

Test #2:

score: 0

Accepted

time: 1ms

memory: 3548kb

input:

2
(([([[([
]]))])]])]

output:

Yes
No

result:

ok 2 token(s): yes count is 1, no count is 1

Test #3:

score: -100

Wrong Answer

time: 14ms

memory: 3608kb

input:

15134
][
)(
)([[
[)([
)][)
]])(
([]([]
]]))][
[([](]
()[))]
][(]](
([()[)
()[]((
[)([)(
]]([[)]]
)[()])]]
))[](([]
](([((]]
))[)][)[
[)])([(]
[()[]))[
)][(]()]
[[((]()]
((]])[[)
])(](]])
)]]()[](
([)[])])
[[)[()](
([[)[[()
[[)([]))
[)[[)[()
))[(([)(
()][)[](]]
[()]([[([[
)[]))][)][
)]([]([(][
[])])(...

output:

Yes
Yes
Yes
Yes
Yes
Yes
Yes
No
Yes
Yes
Yes
Yes
No
Yes
No
Yes
No
No
Yes
Yes
No
Yes
No
No
Yes
No
Yes
Yes
No
No
Yes
No
No
No
No
Yes
No
No
No
No
No
No
Yes
No
No
Yes
Yes
No
No
No
Yes
No
No
No
No
Yes
No
No
No
Yes
Yes
No
No
Yes
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No
No
No
Yes
No
No
No
No
No
No
No
No...

result:

wrong answer expected NO, found YES [106th token]