|
|
back to boardShow all messages Hide all messages[code deleted]
Edited by moderator 13.02.2007 20:57 BubbleSort works in O(n^2) 100 000 ^ 2 = 10 000 000 000
10billion operations. It is defenetely to much.
Use quicksort or heapsort algo's.
Maybe even shellsort will pass TL. qsort will get TLE ..
but STL qsort get AC Why don't you use HASHLIST?
each number is between 1 and 5000.
I can get AC using 0.001 sec.
Edited by author 24.02.2007 08:18 Why don't you use HASHLIST?
each number is between 1 and 5000.
I can get AC using 0.001 sec.
Edited by author 24.02.2007 08:18 What is HASHLIST? How to use it? MY program here:
#include<stdio.h>
int hash[5001];// This is HASHLIST,when a number x appears,increase hash[x],so that the array can be sorted.
int a[100001];
char str[6];
int i,j,k,m,n;
main()
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
hash[a[i]]++;//when a number x appears,increase hash[x],so that the array can be sorted.
}
for(i=1;i<=5000;i++)
{
if(hash[i]>0)
{
for(j=1;j<=hash[i];j++)
a[m+j]=i;
m+=hash[i];//m is to record how many numbers are less then i.
}
}
scanf("%s",str);
scanf("%d",&k);
for(i=1;i<=k;i++)
{
scanf("%d",&j);
printf("%d\n",a[j]);
}
} This is my attempt to use hashlist on Pascal. AC about 0.031. Good luck.
var i,n:longint; k,a,max,l,b,m:integer;
hash,ar,bc:array[1..5001]of integer;
begin
{ TODO -oUser -cConsole Main : Insert code here }
readln(n);
max:=0;
for i:=1 to n do
begin
readln(a);
inc(hash[a]);
if a>max then max:=a;
end;
for i:=1 to max do
if hash[i]>0 then begin l:=l+1; ar[l]:=i; bc[l]:=hash[i]; end;
readln;
readln(k);
l:=0;
for i:=1 to k do
begin
l:=0; m:=0;
readln(b);
while m<b do begin inc(l); m:=m+bc[l]; end;
writeln(ar[l]);
end;
end. Or maybe it is not hash list.. i don`t know exactly. |
|
|
