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. [b]The task : [/b]
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
[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;
}
Someone should sagebomb this thread or ask some World4ch staff to fix this damn Shiichan bug already. I would have even posted in this thread (saging) if not for the idiocy of other posters to bump it.
（￣へ￣） Hello. I am "Mr. Likes To Sage Threads". I do believe this is a thread in need of Sage, so I would like to sage it. That is why my name is "Mr. Likes To Sage Threads".
Name:
Anonymous2010-03-07 15:45
（￣へ￣） Hello. I am "Mr. Likes To Bump Threads". I do believe this is a thread in need of Bump, so I would like to bump it. That is why my name is "Mr. Likes To Bump Threads".
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. [o]The task : [/o]
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
[o]My solution : [/o]
#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;
}
the problem obviously is that the </i> got truncated. I can't think of a way to get bbcode to make an </i> without a matching <i> to come first.
That means the only solutions involve outside help, like greasemonkey or mods. Either that, or /prog/ actually gets tired of it and lets it die on its own. The lattermost solution is the likeliest to happen, unless someone is able to innovate with their BB
>>148
You mean one guy will keep bumping this for two years just to be a faggot? Sure, why not.
Name:
Anonymous2010-03-07 16:31
>>146 the problem obviously is that the </i> got truncated
So how come that there were other attempts at replicating the problem, with other tags, with no success?
Name:
Anonymous2010-03-07 16:46
>>146 That means the only solutions involve outside help, like greasemonkey or mods.
We also can add an unmatched <b>. It's not the solution, but definitely a step in the right direction. Then, an unmatched <u>. Unmatched <span class="o"> would be much harder I'm afraid, but with that problem we better deal when it arises.