QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#555843#5108. Prehistoric ProgramsevirirWA 17ms10236kbC++201.7kb2024-09-10 10:54:172024-09-10 10:54:18

Judging History

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

  • [2024-09-10 10:54:18]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:10236kb
  • [2024-09-10 10:54:17]
  • 提交

answer

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

#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
using ll = long long;
using ii = pair<ll, ll>;
using ld = long double;

struct St
{
    string s;
    int id;
    int net;
    int mn;
    auto operator<=>(const St& o) const
    {
        return tie(mn, net) <=> tie(o.mn, o.net);
    }
};

void fail()
{
    cout<<"impossible\n";
    exit(0);
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);

    int n; cin>>n;
    vector<St> a(n);
    forn(i,0,n)
    {
        string s; cin>>s;
        int sum = 0;
        int mn = 0;
        for (const auto c : s)
        {
            if (c == '(') sum++;
            else sum--;
            mn = min(mn, sum);
        }
        a[i] = {s, i, sum, mn};
    }
    vector<St> a0 = a;
    sort(all(a));
    vector<int> ans;
    ans.reserve(n);
    priority_queue<ii, vector<ii>> q; // (net, id)
    int sum = 0;
    int p = n - 1;  // last unused
    while (sz(ans) < n)
    {
        while (p >= 0 && sum + a[p].mn >= 0)
        {
            q.push({a[p].net, a[p].id});
            p--;
        }
        if (q.empty()) fail();
        auto [net, id] = q.top(); q.pop();
        ans.pb(id);
        sum += net;
    }
    sum = 0;
    forn(i,0,n)
    {
        int mn = a0[ans[i]].mn;
        int net = a0[ans[i]].net;
        if (sum + mn < 0) fail();
        sum += net;
    }
    if (sum != 0) fail();
    forn(i, 0, n) cout << ans[i] + 1 << '\n';

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 17ms
memory: 10236kb

input:

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

output:

impossible

result:

wrong answer you didn't find a solution but jury did