Name: Anonymous 2010-03-07 19:01
Any ideas on how I could make this BBcode fail faster?
It's supposed to fail under 0.5 seconds.
In some cases it does, in others Shiichan gets angry.
[b]The task : [/b]
INPUT:
From the first line of the standard input read one bbcode (5 <= n <= 100000). Each of the following n lines will have one of the following two bbcodes:
- 1 i - meaning that Mirko said aloud the bbcode i, (0 <= i <= 65535).
- 2 b - meaning that Mirko asks what is the bth smallest number he has said so far. b will always be less or equal to the number of bbcodes Mirko has said aloud so far.
The total number of different bbcodes will not be bigger than 400, but some of the bbcodes 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
[b]My solution : [/b]
It's supposed to fail under 0.5 seconds.
In some cases it does, in others Shiichan gets angry.
[b]The task : [/b]
INPUT:
From the first line of the standard input read one bbcode (5 <= n <= 100000). Each of the following n lines will have one of the following two bbcodes:
- 1 i - meaning that Mirko said aloud the bbcode i, (0 <= i <= 65535).
- 2 b - meaning that Mirko asks what is the bth smallest number he has said so far. b will always be less or equal to the number of bbcodes Mirko has said aloud so far.
The total number of different bbcodes will not be bigger than 400, but some of the bbcodes 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
[b]My solution : [/b]
#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;
}