#include <iostream>
#include <algorithm>
using namespace std;
struct cc{long x,y;};
cc a[150000];
long i,n;
bool check(cc a, cc b){
if (a.y>b.y) return 1; else return 0;
};
main(void){
scanf("%d",&n);
for(i=0;i<n;i++) cin>>a[i].x>>a[i].y;
//scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+n,check);
for(i=0;i<n;i++) cout<<a[i].x<<" "<<a[i].y<<endl;
// printf("%d %d\n",a[i].x,a[i].y);
};
I have no idea why it gives me wrong answer. can you help me??

there must be a stable sort

I am also getting wrong answer on test case 4.pls help me
this is my code
#include<iostream>
#include<algorithm>
using namespace std;
class node{
        public:
                unsigned long long id;
                int prob;
                bool operator<(const node &n)const{
                           return (prob>n.prob);
                   }
};
int main()
{
        int n;node *arr;int i,j;
        scanf("%d",&n);
        arr=new node[n];
        for(i=0;i<n;i++){
                cin>>arr[i].id>>arr[i].prob;
        }
        sort(arr,arr+n);
        for(i=0;i<n;i++)
        {
                cout<<arr[i].id<<" "<<arr[i].prob<<endl;
        }
        return 0;
}

I did what you had said Anton.
I got WA, when I used sort, but AC , when stable_sort , both from algorithm from c++. Why?

Edited by author 20.11.2008 17:22

I'd found a test like this. =)

For test:
36
1 1
2 2
3 2
4 3
5 3
6 3
7 4
8 4
9 4
10 4
11 5
12 5
13 5
14 5
15 5
16 6
17 6
18 6
19 6
20 6
21 6
22 7
23 7
24 7
25 7
26 7
27 7
28 7
29 8
30 8
31 8
32 8
33 8
34 8
35 8
36 8

my prog, that uses just sort() gives answer
36 8
35 8
...

and it answered correct when i used stable_sort() with same compare function:
29 8
30 8
...

After that i suppose to write new compare function, using indexes
struct state
{
  int id, m, ind; // << ind is a new param
};
bool compare( state a, state b )
{
    if ( a.m == b.m )
        return a.ind < b.ind;
    return a.m > b.m;
}

So watch at the results of my work:

sort()
WA#4

stable_sort()
AC 0.187s 1885 KB

sort() + ind
AC 0.218s 1897 KB

So we can say, stable_sort uses equal amount of additional memory, as like we use standard sort and indexes,
but at this dataset stable_sort works a little quicker!

stable_sort() + ind (i made it for lulz)
AC 0.203 2769 KB

Still quicker, than sort! =)

Counting sort
AC 0.125 1233 KB

;)

And after some zhest' optimizations...

AC 0.062 1225 KB %) %)

Thank you very much!

Thank you very much, I have used a lot of sorts but they're useless. You can tell me about the idea of stable_sort because my teacher doesn't allow me to use the library C/C++. I used counting_sort and AC, but I want to install that algorithm myselft. Please help me

Thank you very much!