ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1037. Memory Management

Brute force WA#3 ???
Posted by bsilver.info 6 Mar 2008 13:54
Why do I get WA on test #3 ?

I'm using a simple algorithm which stores the last time a lock was requested in a vector a[].

for the access request it checks whether the memory block #i has a request more recent than 600s. if yes it writes '+' and changes the last request time else it writes -.

for the allocation request it searches for the first memory block that hasn't been accessed for at least 600s, writes it's number and changes the last request time.

initially all memory blocks have a last reuest time of -601s so they are all free.

i tried changing the input and output method a lot of times (for some problems it works) and checked my program several times with test in this discussion forum and of my own and the program gives the right answers.

can someone fin where i'm wrong?

why do i get WA? i think i should have got TLE for the worst of cases because the algorithm is kind of slow, but not WA.

also here is the source code for my program:



#include <stdio.h>

long int a[30002];

int main(void)
{
    long int i,timp;
    char c,buf;
    for(i=0;i<=30000;i++)
                         a[i]=-601;
    scanf("%ld %c",&timp,&c);
    if(c=='.')
              scanf("%ld",&i);
    while(!feof(stdin))
    {
                       if(c=='.')
                       {
                                 if(((timp-a[i]))<600)
                                 {
                                                           a[i]=timp;
                                                           printf("+\n");
                                                           }
                                 else
                                     printf("-\n");
                                 }
                       else
                           if(c=='+')
                           {
                                     for(i=1;(((timp-a[i]))<600);i++);
                                     printf("%ld\n",i);
                                     a[i]=timp;
                                     }
                       scanf("%ld %c",&timp,&c);
                       if(feof(stdin))
                                      return 0;
                       if(c=='.')
                                 scanf("%ld",&i);
                       }
    return 0;
}