QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#69634	#5108. Prehistoric Programs	ricky0129	WA	28ms	7268kb	C++14	1.9kb	2022-12-29 03:29:58	2022-12-29 03:30:01

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-29 03:30:01]
评测

测评结果：WA
用时：28ms
内存：7268kb

查看

[2022-12-29 03:29:58]
提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second

const int MOD = (int)1e9+7;

struct obj{
    string val;
    int idx;
    int sum, left,right;
    obj(int sum=0,int left=0,int right=0) : sum(sum), left(left), right(right) {} 
    bool operator< (obj lhs) const {
        if(sum<=0 == lhs.sum<=0){
            if(sum<=0){
                return tie(left,sum)<tie(lhs.left,lhs.sum);
            }
            else return tie(right,sum)<tie(lhs.right,lhs.sum);
        }
        return tie(sum)<tie(lhs.sum);
    }
};
int main()
{
    int n;
    cin>>n;
    vector<obj> A;
    FOR(i,n){
        string in;
        cin>>in;
        int curr = 0;
        int mini = INT_MAX;
        FOR(j,sz(in)){
            if(in[j]=='(') curr++;
            else curr--;
            mini = min(mini,curr);
        }
        int maxi = INT_MAX;
        curr = 0;
        for(int j=sz(in)-1;j>=0;j--){
            if(in[j]==')') curr++;
            else curr--;
            maxi = min(maxi,curr);
        }
        obj x = obj(obj(curr,-mini,maxi));
        x.idx = i+1;
        x.val = in;
        A.pb(x);
    }
    sort(A.begin(),A.end());
    bool check = true;
    int open = 0;
    int close = 0;
    for(auto x: A){
        string in = x.val;
        FOR(i,sz(in)){
            if(in[i]==')') close++;
            else open++;
            if(close>open) check = false;
        }
        if(open!=close) check = false;
    }
    if(!check) cout<<"impossible\n";
    else{
        for(auto x: A){
            cout<<x.idx<<endl;
        }
    }

    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0

Wrong Answer

time: 28ms

memory: 7268kb

input:

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

output:

impossible

result:

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