I tried implementing mergesort which probably had recursion depth runtime error; bisect insertion to save some memory, but too slow for python list (perhaps a good alternative if I have access to pointer?); heapq is much faster but instable. What are other options?

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    pair<int ,int > a[150000];
    for(int i=0;i<n;i++)
    {
        cin >> a[i].first >> a[i].second;
    }
    for(int i=100;i>=0;--i)
    {
        for(int j=0;j<n;j++)
        {
            if(i==a[j].second) cout << a[j].first << " " << a[j].second << endl;
        }
    }

}

Help me please, if you can
I wrote a program, but i got rt#4 i don't know why
I tried different tests(M=0;M=100 and other) but it was all in vain
Very grateful for any help!
Sorry for bad English

Edited by author 03.12.2017 20:04

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<pair<int, int> > v;
    int x, p;
    for(int i = 1; i <= n; i ++)
    {
        cin >> x >> p;
        v.pb({p, x});
    }
    sort(v.begin(), v.end());
    reverse(v.begin(), v.end());
    for(int i = 0; i < n; i ++)
    {
        cout << v[i].second << " " << v[i].first << "\n";
    }
}
But it is same sort

I used stable sort from STL and got AC

Pls halp...

var
  i, n: integer;
  id:array of longint;
  ball: array of integer;

procedure qSort(var ar: array of integer; ra:array of longint);
  procedure sort(var ar: array of integer; low, high: integer; ra:array of longint);
  var
    i, j: integer;
    m, wsp: integer;
    b: longint;
  begin
    i := low; j := high; m := ar[(i + j) div 2];
    repeat
      while ar[i] < m do Inc(i);
      while ar[j] > m do Dec(j);
      if i <= j then begin
        wsp := ar[i]; ar[i] := ar[j]; ar[j] := wsp;
        b := ra[i]; ra[i] := ra[j]; ra[j] := b;
        Inc(i); Dec(j);
      end;
    until i > j;
    if low < j then sort(ar, low, j, ra);
    if i < high then sort(ar, i, high, ra);
  end;
begin
  sort(ar, 0, High(ar), ra);
end;

begin
  read(n);
  setlength(id,n);
  setlength(ball,n);
  for i := 0 to n-1 do
    read(id[i], ball[i]);
  qSort(ball, id);
  for i := n-1 downto 0 do
    writeln(id[i], ' ', ball[i]);
end.

What's wron? Halp pleese!

All mentioned solutions cause TLE.

Нашел ошибку. =)

Edited by author 12.05.2014 09:33

#include <iostream>
using namespace std;

int main()
{
    long N;
    cin >> N;
    long **array = new long*[N];
    for (long i = 0; i < N; i++)
    {
        array[i] = new long[2];
        long temp, temp2;
        cin >> temp >> temp2;
        array[i][0] = temp;
        array[i][1] = temp2;
    }
    cout << endl << endl;

    long l, r, i, k, buf;
    k = l = 0;
    r = N - 2;
    while (l <= r)
    {
        for (i = l; i <= r; i++)
            if (array[i][1] < array[i + 1][1])
            {
                swap(array[i], array[i + 1]);
                k = i;
            }
        r = k - 1;
        for (i = r; i >= l; i--)
            if (array[i][1] < array[i + 1][1])
            {
                swap(array[i], array[i + 1]);
                k = i;
            }
        l = k + 1;
    }
        for (long i = 0; i < N; i++)
        {
            cout << array[i][0] << " " << array[i][1] << endl;
        }
        return 0;
    }

What is wrong with it?( I use bubbleshaker sort.

I think, i do all rigth, but i've WA1=((
I don't understand output type, that's mean what me should to print. Sorry for my English...

var a,b:array[1..15000]of longint; asd,asd1,n,i,j:longint;
begin
read(n);
for i:=1 to n do read(a[i],b[i]);

for i:=1 to n-1 do
  for j:=i+1 to n do
    if b[i]<b[j] then begin
                      asd:=b[i];
                      b[i]:=b[j];
                      b[j]:=asd;
                      asd1:=a[i];
                      a[i]:=a[j];
                      a[j]:=asd1;
                      end;

for i:=1 to n do begin write(a[i],' ',b[i]);writeln;end;
end.

Тут кто нибудь вообще прощёл тест №11 на Java пользуясь именно Bubble Sort? Что то мне подсказывает что это вообще невозможно с такими ограничениями времени. Но в таком случае, почему в задаче упоминается именно пузырьковый поиск? Или всё таки это возможно, а я где то дико туплю?

import java.io.*;
public class Timus {
        public static void main (String[] args) throws IOException
        {
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            PrintWriter out = new PrintWriter (new OutputStreamWriter(System.out));

            int N = Integer.parseInt(in.readLine()), bufer;
            int ID[] = new int[N];
            byte M[] = new byte[N];

            for (int i = 0; i<N; i++)
            {
                String[] s = in.readLine().split(" ");
                ID[i] = Integer.parseInt(s[0]);
                M[i] = Byte.parseByte(s[1]);
            }

            for (int i = 0; i < N-1; i++)
                for (int j = N-1; j > i; j--)
                    if (M[j]>M[j-1])
                    {
                        bufer = M[j];
                        M[j] = M[j-1];
                        M[j-1] = (byte) bufer;
                        bufer = ID[j];
                        ID[j] = ID[j-1];
                        ID[j-1] = bufer;
                    }

            for (int i = 0; i < N; i++)
                out.print("\n" + ID[i] + " " + M[i]);

            out.flush();
        }
}

In this task, use StreamTokenizer instead Scanner, otherwise will be TLE

I use LINQ to sort this sequence, it works pretty well on all tests i found.
Any ideas why it works wrong on test 4?



using System;
using System.Linq;

namespace Таблица_результатов
{
    class Program
    {

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] lines = new string[n];
            for (int i = 0; i < n; i++) { lines[i] = Console.ReadLine(); }

            var a = lines
                 .Select(x => x.Split())
                 .ToArray()
                 .OrderByDescending(x => x[1]);


            foreach (var x in a)
            {
                Console.WriteLine(x[0] + " " + x[1]);
            }
        }
    }
}

#include<stdio.h>
void merge(int a[],int b[],int c[],int d[],int left,int mid,int right)
{
    int i=left,j=mid+1;
    int k=left;
    while((i<=mid)&&(j<=right))
    {
        if(a[i]>=a[j])
        {b[k++]=a[i++];
        k--;
        i--;
        d[k++]=c[i++];}
        else
        {b[k++]=a[j++];
        k--;
        j--;
        d[k++]=c[j++];}
    }
    if(i>mid)
        for(int q=j;q<=right;q++)
        {b[k++]=a[q];
    k--;
         d[k++]=c[q];
    }
    else if(j>right)
        for(int q=i;q<=mid;q++)
        {b[k++]=a[q];
    k--;
    d[k++]=c[q];}
    for (int l = left;l <= mid;l++) {
        a[l] = b[l];
        c[l]=d[l];
    }
    for (int l = mid+1;l <= right;l++) {
        a[l] = b[l];
        c[l]=d[l];
    }
}
void mergesort(int a[],int b[],int c[],int d[],int left,int right)
{
    if(left<right)
    {
        int mid = (left + right) / 2;
        mergesort(a,b,c,d,left,mid);
        mergesort(a,b,c,d,mid+1,right);
        merge(a, b,c,d, left, mid, right);
    }
}
int main()
{
    int n,i;
    int c[15000],a[15000],b[15000],d[15000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&c[i]);

        scanf("%d",&a[i]);
    }
    mergesort(a,b,c,d,0,n-1);
    for(i=0;i<n;i++)
    {
        printf("%d %d\n",d[i],b[i]);
    }
    fflush(stdin);
    getchar();
    return 0;
}

following is my solution in C.I have used qsort() function of library stdlib.I have checked it on all test cases but still I am not able to figure out which test case is getting wrong..please help...i have really spend a lot of time on this.
#include<stdio.h>
#include<stdlib.h>
struct TwoInt
{
    long int a;
    int b;
};
typedef struct TwoInt Int;
Int arr[200000];
int cmpfnc(const void* a,const void* b)
{
 const int p=((const Int*)a)->b;
 const int q=((const Int*)b)->b;
 if(p>q)
  return q-p;
 else
  {
     if(p<q)
  return q-p;

  }
  return 0;

}
int main()
{
long int n;
scanf("%ld",&n);
long int i=0;
for(i=0;i<n;i++)
scanf("%ld %d",&(arr[i].a),&(arr[i].b));

qsort(arr,n,sizeof(Int),cmpfnc);

for(i=0;i<n;i++)
printf("%ld %d\n",arr[i].a,arr[i].b);
return 0;
}

Here is my Solution. As this problem is related to stable sort and there is  built in stable_sort function in c++ so it has become easier


#include <bits/stdc++.h>
using namespace std;
bool compare( const pair<long long int,long long int>& x, const pair<long long int, long long int>& y )
{

    return (x.second>y.second);

}
int main()
{
    vector<pair<long long int,long long int> >a;
    long long int n,i,j,b,c;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>b>>c;
        a.push_back(pair<long long int,long long int>(b,c));
    }
    stable_sort(a.begin(),a.end(),compare); //must include stable_sort
    vector<pair<long long int,long long int> >::iterator p;
    for(p=a.begin();p!=a.end();p++)
    {
        cout<<p->first<<" "<<p->second<<endl;
    }
    return 0;



}

Edited by author 11.06.2016 01:55

here is my code

import java.io.PrintWriter;
import java.util.*;

public class Problem1100 {

    public static class Busket extends LinkedList<Long>{}

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int times = in.nextInt();
        Busket[] list = new Busket[100];
        long id =0;
        int score =0;
        for(int i =0;i<times;i++){
            id = in.nextLong();
            score = in.nextInt();
            boolean insert=false;
            if(list[score]==null){
                Busket busket =  new Busket();
                busket.add(id);
                list[score]=busket;
            } else{
                list[score].add(id);
            }
        }

        StringBuffer result = new StringBuffer();

        for(int i = list.length-1;i>=0; i--){
            Busket busket =list[i];
            if(busket!=null)
            for(Long mId: busket) {
                result.append(mId);
                result.append(" ");
                result.append(i);
                result.append("\n");
            }
        }
        out.println(result.toString());
        out.flush();
    }
}

Edited by author 24.05.2016 13:57

Edited by author 24.05.2016 14:01

Edited by author 24.05.2016 14:09

Edited by author 24.05.2016 14:11

You just need an array with 100 elements so in every position M, you add the ID using a dynamic structure such as "vector" in C++. (Theoretical complexity O(n)) Now you go from 100 to 0 and then print every element from each position M.

Edited by author 23.04.2016 15:06

program timus_1100;
const
  maxn=150000;
var
  ID:array[1..maxn]of longint;
  np:array[1..maxn]of byte;
  n:longint;
  i,j:longint;
begin
  readln(n);
  for i:=1 to n do
    readln(ID[i],np[i]);
  for i:=100 downto 0 do
    for j:=1 to n do
      if np[j]=i then
        writeln(ID[j],' ',np[j]);
end.

Edited by author 22.01.2016 17:19