Return Styles: Pseud0ch, Terminal, Valhalla, Blue Moon.

Pages: 1-

Any ideas on how I could make this program run faster?

Name: Anonymous 2017-08-26 23:58

Any ideas on how I could make this program run faster?
It's supposed to run under 0.5 seconds.
In some cases it does, in others it fails.
The task : [/u]

INPUT:
From the first line of the standard input read one integer (5 <= n <= 100000). Each of the following n lines will have one of the following two formats:

- 1 a - meaning that Mirko said aloud the number a, (0 <= a <= 65535).
- 2 k - meaning that Mirko asks what is the kth smallest number he has said so far. k will always be less or equal to the number of numbers Mirko has said aloud so far.

The total number of different number will not be bigger than 400, but some of the numbers can repeat!

OUTPUT:
To the standard output write one line for each of the 2 k inputs. Representing the kth smallest number at that moment.


Input:
7
1 0
1 1
1 5
2 1
2 3
1 2
2 3

Output:
0
5
2


My solution :

#include <stdio.h>
int main(){
unsigned short int * a;
unsigned int n,j,x,y;
int m=-1;
scanf("%u",&n);
a=new unsigned short int[n];
while (n>0){
n=n-1;
scanf("%u %u",&x,&y);
if (x==1){
m=m+1;
j=m;
a[j]=y;
while((j>0)&&(a[j]<a[j-1])){
y=a[j-1];
a[j-1]=a[j];
a[j]=y;
j=j-1;
}

}
else printf("%u\n",a[y-1]);
}
delete [] a;
return 0;
}

Name: Anonymous 2017-08-27 0:44

I read it twice and still don't get it.

Name: Anonymous 2017-08-27 7:54

Sepples doesn't make Bubble Sort run fast.

Name: Anonymous 2017-08-27 8:15

buy a better proc
moar RAM
install gentoo

Name: Anonymous 2017-08-27 8:49

>>3
This.

Name: Anonymous 2017-08-27 12:50

read this thread for inspiration https://archive.tinychan.org/read/prog/1250478524

Name: Anonymous 2017-08-28 0:43

Some inputs are tricky, what is the largest n you've been given?

Name: Anonymous 2017-08-28 1:07

try using -O3

Name: Anonymous 2017-08-28 6:19

>>3
The code does an insertion sort

Name: Anonymous 2017-08-28 13:25

zoomzoom

//a[j]=y;
while((j>0)&&(y<a[j-1])){
a[j]= a[j-1];
j=j-1;
}
a[j] = y;

Name: Anonymous 2017-08-28 13:41

dubsdubs

Name: Anonymous 2017-08-28 16:28

>>1
For large numbers of insertions, something with a O(login) insertion might work better, like a skip list or binary tree of some kind

Name: Anonymous 2017-08-29 3:13

>>12
O(login)
Also known as OAuth.

Name: Anonymous 2017-08-30 14:00

who's Mirko?

Name: Anonymous 2017-08-30 20:40

>>14
Mirko (Cyrillic script: Мирко) is a masculine given name of South Slavic origin.

Name: Anonymous 2017-08-31 10:39

>>15
Whom are you quoting?

Name: Anonymous 2017-09-02 0:18

bump

Name: Anonymous 2017-09-02 6:51

intra-k amortized?

kn-1z x x x x x knz2

Est knz2 @ kn-1z2 - sum(x < kn-1z2)

Name: Anonymous 2017-09-02 12:18

partial lasersort should kill it lol

Don't change these.
Name: Email:
Entire Thread Thread List