Advertisement
Guest User

Problem 10474 - Where is the Marble? (time 0.052)

a guest
Dec 14th, 2010
644
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.86 KB | None | 0 0
  1. /*
  2.     Problem 10474 - Where is the Marble? (time 0.052)
  3.     URL: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1415
  4.     Alexey Solodovnikov (alexey.solodovnikov@gmail.com)
  5. */
  6.  
  7.  
  8. #include <stdio.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <time.h>
  12.  
  13. #define SIZE 16*1024
  14. #define N    10001
  15. static unsigned int values[N];
  16. static int  buffer_size = 0;
  17. static int  buffer_pos  = -1;  
  18. static char buffer[SIZE];
  19.  
  20. unsigned int readInt()
  21. {
  22.     unsigned int value  = 0;
  23.     unsigned int digits = 0;
  24.     char b;
  25.    
  26.     if (buffer_pos == -1)
  27.     {
  28.         buffer_size = fread(buffer, 1, SIZE, stdin);
  29.         buffer_pos  = 0;
  30.     }
  31.  
  32.     while(buffer_size > 0)
  33.     {
  34.  
  35.         if (buffer_pos == buffer_size)
  36.         {
  37.             buffer_size = fread(buffer, 1, SIZE, stdin);
  38.             buffer_pos = 0;
  39.         }
  40.  
  41.         while(buffer_pos < buffer_size)
  42.         {
  43.                 b = buffer[buffer_pos++];  
  44.                     if (b == '\n' || b == ' ')
  45.             {
  46.                 return value;
  47.             }
  48.                     else
  49.             {
  50.                         value = value*10 + (b - '0');
  51.                 digits++;
  52.             }
  53.         }
  54.     }
  55.     return value;
  56. }
  57.  
  58. int main(int argc, char **argv)
  59. {
  60.  
  61.     unsigned int  n, q, num, max, c = 0;
  62.  
  63.     while(1)
  64.     {
  65.         c++;
  66.         n = readInt();
  67.         q = readInt();
  68.  
  69.         if(n==0 && q==0) break;
  70.  
  71.         max = 0;
  72.         memset(values, 0, N * sizeof(unsigned int));       
  73.        
  74.         for(unsigned int i=0; i<n; i++)
  75.         {
  76.             num = readInt();
  77.             values[num]++;
  78.             if(num > max) max = num;
  79.         }
  80.  
  81.         unsigned int pos = 1, temp;
  82.         for(unsigned int i=0; i <= max; i++)
  83.         {
  84.             if(values[i] !=0){
  85.                 temp = values[i];
  86.                 values[i] = pos;
  87.                 pos += temp;
  88.             }
  89.            
  90.         }
  91.        
  92.         printf("CASE# %d:\n", c);
  93.         unsigned qval;
  94.         for(unsigned int i=0; i<q; i++)
  95.         {
  96.             qval = readInt();
  97.             int ret = values[qval];
  98.             if(ret == 0)
  99.                 printf("%d not found\n", qval);
  100.             else
  101.                 printf("%d found at %d\n", qval, ret);
  102.         }
  103.     }
  104.     return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement