QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#66023	#5108. Prehistoric Programs	bili2002^#	WA	3ms	4284kb	C++17	3.5kb	2022-12-06 00:06:25	2022-12-06 00:06:27

Judging History

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

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

[2022-12-06 00:06:27]
评测

测评结果：WA
用时：3ms
内存：4284kb

查看

[2022-12-06 00:06:25]
提交

answer


#include <bits/stdc++.h>
#define f first
#define s second
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back

using namespace std;
using ll = long long;

template<class T, class T2> inline bool chkmax(T &x, const T2 & y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 & y) { return x > y ? x = y, 1 : 0; }
template<class T, class T2> inline istream &operator>>(istream &is,       pair<T, T2> &p)             { is>>p.f>>p.s;        return is; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const pair<T, T2> &p)             { os<<p.f<<' '<<p.s;   return os; }
template<class T>           inline istream &operator>>(istream &is,       vector<T> &v)               { for (auto &id : v)   is>>id;       return is; }
template<class T>           inline ostream &operator<<(ostream &os, const vector<T> &v)               { for (auto id : v)    os<<id<<'\n';  return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const map<T, T2> &m)              { for (auto id : m)    os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const unordered_map<T, T2> &um)   { for (auto id : um)   os<<id<<'\n'; return os; }
template<class T>           inline ostream &operator<<(ostream &os, const list<T> &l)                 { for (auto id : l)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const set<T> &s)                  { for (auto id : s)    os<<id<<' ';  return os; }
template<class T>           inline ostream &operator<<(ostream &os, const unordered_set<T> &us)       { for (auto id : us)   os<<id<<' ';  return os; }
const long long INF = 1e18;
const bool hasTests = 0;

struct par {
    int op, cl;
    int id;
    bool neg;
    int highestMin;

    bool operator<(const par& oth) {
        if (!neg && oth.neg) {
            return true;
        }
        if (neg && !oth.neg) {
            return false;
        }
        return highestMin < oth.highestMin;
    }
};

vector<par> p;

bool pos;
vector<int> ans;
int n;

void input() {
    cin>>n;
    p.resize(n);

    string s;
    for (int i=0; i<n; i++) {
        cin>>s;
        p[i].id = i;
        p[i].neg = false;
        for (auto curr : s) {
            if (curr == '(') {
                p[i].op++;
            } else {
                p[i].cl++;
            }
            if (p[i].op < p[i].cl) {
                p[i].neg = true;
            }
            p[i].highestMin = min(p[i].highestMin, p[i].op - p[i].cl);
        }
    }
}

void output() {
    if (!pos) {
        cout<<"impossible\n";
        return;
    }

    cout<<ans<<endl;
}

void solve() {
    sort(all(p));

    pos = true;
    int cntOp = 0, cntCl = 0;
    for (auto& curr : p) {
        //cout<<curr.id<<' '<<cntOp + curr.highestMin<<' '<<cntCl<<endl;
        if (cntOp + curr.highestMin < cntCl) {
            pos = false;
            break;
        }

        cntOp += curr.op;
        cntCl += curr.cl;
        ans.pb(curr.id + 1);
    }

    if (cntOp != cntCl) {
        pos = false;
    }
}

void start() {
    int t = 1;
    if (hasTests) {
        cin>>t;
    }

    for (int i=1; i<=t; i++) {
        input();
        solve();
        //cout<<"Case #"<<i<<": ";
        output();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    start();
    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 3ms

memory: 4284kb

input:

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

output:

result:

ok good plan

Test #2:

score: -100

Wrong Answer

time: 3ms

memory: 3364kb

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

impossible

result:

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