501  Black Box
Moderator: Board moderators
501  Black Box
bacause I `m afraid my program will get Time Exceed!

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
If you are serious about Computer Science, you should pick up a couple of algorithm books (Dijkstra, Skienka, the MIT introduction one). They should give you some basic idea of the tools at your disposal. Then you should be able to apply the right one or even DEVELOP it. After all, Computer Science is only Applied Computational Mathematics. Induce and deduce:)

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
Re: for 501 : Is there any efficient algorism to be used ?
1) Two HeapsAnderson wrote:bacause I `m afraid my program will get Time Exceed!
2) RedBlack Tree

 A great helper
 Posts: 284
 Joined: Thu Feb 28, 2002 2:00 am
 Location: Germany
 Contact:
hello all,
I have posted my code here,
because i have tried in many ways to get ac but
i have got w ans.
please check it.
code:[c][/c][/cpp]
I have posted my code here,
because i have tried in many ways to get ac but
i have got w ans.
please check it.
code:[c]
Code: Select all
[b]
#include<stdio.h>
#define NUM 30100
main()
{
long long int m,i,j,
k,n,l,s,p,
c[NUM],d[NUM],a[NUM];
scanf("%lld%lld",&m,&n);
s=0;
for(i=0;i<m;i++)
scanf("%lld",&c[i]);
for(i=0;i<n;i++)
scanf("%lld",&d[i]);
l=p=0;
for(i=0;i<m;i++)
{
for(j=0;j<s;j++)
if(a[j]>c[i])
break;
if(j==s) a[j]=c[i],s++;
else
{
for(k=s;k>j;k)
a[k]=a[k1];
a[j]=c[i];s++;
}
a[s]=0;
while(1)
{
if(d[l]==n) break;
if(d[l]!=(i+1)) break;
l++;
p++;
printf("%lld\n",a[p1]);
}
}
return 0;
}
any help is welcome[/b]
"Everything should be made simple, but not always simpler"

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
501  Black Box : What should be the data structure ?
I used insertion sort in this problem due to the fact that each time a new value is entered into a sorted list. But this procedure recieves a TLE. Can someone tell me what data structure should I use to speed the things up?
You should never take more than you give in the circle of life.

 Experienced poster
 Posts: 154
 Joined: Sat Apr 17, 2004 9:34 am
 Location: EEE, BUET
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Maybe there is something I don't understand about this problem. I tried coding it twice, and I always get WA. Could anyone give me a hint? I simply use a set to store the numbers and an iterator into that set pointing the the last number that I accessed. I use a set of pairs to take care of duplicate elements.
Code: Select all
Oll Korrect now.
Last edited by Abednego on Sun Apr 24, 2005 8:26 pm, edited 1 time in total.
If only I had as much free time as I did in college...
I don't know if your algorithm is correct, I'm no C++ guy.
The problem as I implemented it: with each "ADD" query add the number to your data structure. With the ith "GET" query print the ith smallest number in the data structure.
The problem comes from NEERC' 1996 regionals. You can use the tests at http://www.acm.inf.ethz.ch/ProblemSetAr ... NERC/1996/ as a last resort.
The problem as I implemented it: with each "ADD" query add the number to your data structure. With the ith "GET" query print the ith smallest number in the data structure.
The problem comes from NEERC' 1996 regionals. You can use the tests at http://www.acm.inf.ethz.ch/ProblemSetAr ... NERC/1996/ as a last resort.