QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#66051#5108. Prehistoric Programsrumen_m#WA 636ms3968kbC++141.3kb2022-12-06 02:29:142022-12-06 02:29:16

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 02:29:16]
  • 评测
  • 测评结果:WA
  • 用时:636ms
  • 内存:3968kb
  • [2022-12-06 02:29:14]
  • 提交

answer

# include <bits/stdc++.h>
const long long MAXN = 1e6+5;
using namespace std;
struct ww
{
    int id;
    int ends;
    int nms;
};
ww seq[MAXN];
bool cmp(ww i, ww j)
{
    if(i.nms >= 0)
    {
        if( j.nms < 0) return true;
        return i.ends >= j.ends;
    }
    if(j.nms >= 0) return false;
    if(i.ends > 0)
    {
        if(j.ends <= 0) return true;
        return i.ends <= j.ends;
    }
    if(j.ends > 0) return false;
    return i.nms >= j.nms;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    string s;
    int i,j;
    cin>>n;
    for(i = 1; i <= n; i++)
    {
        cin>>s;
        seq[i].id=  i;
        seq[i].nms = 0;
        seq[i].ends = 0;
        for(char ch:s)
        {
            if(ch=='(')
            {
                seq[i].ends++;
            }else
                seq[i].ends--;
            seq[i].nms = min(seq[i].nms,seq[i].ends);
        }
    }
    sort(seq+1,seq+n+1,cmp);
    int currD=0;

    for(i  =1; i <= n; i++)
    {
       if(currD + seq[i].nms < 0){cout<<"impossible\n";return 0;}
       currD+=seq[i].ends;
    }
    if(currD!=0){cout<<"impossible\n";return 0;}
    for(i = 1; i <=n; i++)
        cout<<seq[i].id<<endl;

        }

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

impossible

result:

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