QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#89244#5108. Prehistoric ProgramsHiperEgWA 18ms3968kbC++201.2kb2023-03-19 13:21:592023-03-19 13:22:00

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-19 13:22:00]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:3968kb
  • [2023-03-19 13:21:59]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int main()
{
    vector<pair<pair<int, int>, int>> v;

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;

        int balance = 0, menor = 1;

        for (auto ch : s)
        {
            if (ch == ')')
            {
                balance--;
                if (balance < menor)
                {
                    menor = balance;
                }
            }

            else
            {
                balance++;
            }
        }

        v.push_back({{-menor, -balance}, i});
    }

    sort(v.begin(), v.end());

    //for (auto& s : v) cout << s.first.first << " " << s.first.second << " " << s.second << '\n';

    int balanco = 0;
    bool poss = true;

    for (auto& s : v)
    {
        int m, b;
        tie(m, b) = s.first;
        m = -m;
        b = -b;

        if (balanco+m < 0 or balanco+b < 0) { poss = false; break; }
        balanco+=b;
    }

    if (!poss or balanco != 0) cout << "Impossible\n";
    else
    {
        for (auto& s : v)
        {
            int c = s.second;
            cout << c << '\n';
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 18ms
memory: 3968kb

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

Impossible

result:

wrong answer wrong output