ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1745. Yet Another Answer

One of the correct sorting function
Posted by vectorlmn 31 Mar 2025 12:30
Becuase of edge cases,this problem take me many hours.
So I put one correct sorting function here.
struct ND{// Single bracket sequence
    int len,mn=0;
    int cnt=0;
    int id;
// len is the length of the bracket sequence
// if we define '(' as +1,and ')' as -1,the minimum prefix sum of the bracket sequence is mn.
// and the total sum of the sequence is cnt
// id is the index of the bracket sequence in the given input.
}nd[maxn];
bool swap(ND& a,ND& b){
        if(a.cnt>=0&&b.cnt<0)return 1;// a first
        if(a.cnt<0&&b.cnt>=0)return 0;// b first
        if(a.cnt>=0)return -a.mn<-b.mn;
        return -b.mn+b.cnt<-a.mn+a.cnt;
}