patterncppMinor

UVA 10474 - "Where is the marble?" time limit

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

themarblelimitwhere10474timeuva

Problem

I have a problem from UVA online judge here. I have read it tons of times, and as they said, I have to get the answer really fast.

I have used a binary search and std::sort, but I am still having a time error. I don't know any faster way of searching on an array other than binary search.

Any feedback please?

#include 
#include 
#include 

int n,q,vec[100000];
int inicio,final,medio,busca;
int cont;
int busquedabinaria()
{

    //busqueda binaria
    std::sort(vec,vec+n);
    inicio=0;
    final=n-1;
    medio=(inicio+final)/2;

    while(inicio busca)
            final = medio - 1;
        else if (vec[medio] 0)
                {
                    res--;
                }
                printf("%d found at %d\n",busca,res+1);

        }
            else 
                printf("%d not found\n",busca);

        }

    }

    return 0;
}

Solution

Your solution is slow because it performs the sorting before every binary search! Just move the sorting to the line above the

printf("CASE# %d:\n",cont+1);

and you'll see the difference.

I also add my solution just to see what's possible to optimize (it uses custom int reader, without sort and the binary search):

#include 
#include 
#include 
#include 

#define SIZE 16*1024
#define N    10001
static unsigned int values[N];
static int  buffer_size = 0;
static int  buffer_pos  = -1;   
static char buffer[SIZE];

unsigned int readInt()
{
    unsigned int value  = 0;
    unsigned int digits = 0;
    char b;

    if (buffer_pos == -1)
    {
        buffer_size = fread(buffer, 1, SIZE, stdin);
        buffer_pos  = 0;
    }

    while(buffer_size > 0)
    {

        if (buffer_pos == buffer_size)
        {
            buffer_size = fread(buffer, 1, SIZE, stdin);
            buffer_pos = 0;
        }

        while(buffer_pos  max) max = num;
            if(num < min) min = num;
        }

        unsigned int pos = 1, temp;
        for(unsigned int i=min; i <= max; i++)
        {
            if(values[i] !=0){
                temp = values[i];
                values[i] = pos;
                pos += temp;
            }

        }

        printf("CASE# %d:\n", c);
        unsigned qval;
        for(unsigned int i=0; i<q; i++)
        {
            qval = readInt();
            int ret = values[qval];
            if(ret == 0) 
                printf("%d not found\n", qval);
            else 
                printf("%d found at %d\n", qval, ret);
        }
    }
    //printf("Time (ms): %ld\n", clock()-time);
    return 0;
}

Code Snippets

printf("CASE# %d:\n",cont+1);

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define SIZE 16*1024
#define N    10001
static unsigned int values[N];
static int  buffer_size = 0;
static int  buffer_pos  = -1;   
static char buffer[SIZE];

unsigned int readInt()
{
    unsigned int value  = 0;
    unsigned int digits = 0;
    char b;

    if (buffer_pos == -1)
    {
        buffer_size = fread(buffer, 1, SIZE, stdin);
        buffer_pos  = 0;
    }

    while(buffer_size > 0)
    {

        if (buffer_pos == buffer_size)
        {
            buffer_size = fread(buffer, 1, SIZE, stdin);
            buffer_pos = 0;
        }

        while(buffer_pos < buffer_size) 
        {
                b = buffer[buffer_pos++];   
                    if (b == '\n' || b == ' ') 
            {
                return value;
            }
                    else
            {
                        value = value*10 + (b - '0');
                digits++;
            }
        }
    }
    return value;
}

int main(int argc, char **argv)
{
    long time = clock();

        char buffer[8192];
        setvbuf(stdout, buffer, _IOFBF, sizeof(buffer));         
    unsigned int  n, q, num, max, min, c = 0;

    while(1)
    {
        c++;
        n = readInt();
        q = readInt();

        if(n==0 && q==0) break;

        max = 0;
        min = N;
        memset(values, 0, N * sizeof(unsigned int));        

        for(unsigned int i=0; i<n; i++)
        {
            num = readInt();
            values[num]++;
            if(num > max) max = num;
            if(num < min) min = num;
        }

        unsigned int pos = 1, temp;
        for(unsigned int i=min; i <= max; i++)
        {
            if(values[i] !=0){
                temp = values[i];
                values[i] = pos;
                pos += temp;
            }

        }

        printf("CASE# %d:\n", c);
        unsigned qval;
        for(unsigned int i=0; i<q; i++)
        {
            qval = readInt();
            int ret = values[qval];
            if(ret == 0) 
                printf("%d not found\n", qval);
            else 
                printf("%d found at %d\n", qval, ret);
        }
    }
    //printf("Time (ms): %ld\n", clock()-time);
    return 0;
}

Context

StackExchange Code Review Q#16050, answer score: 3

Revisions (0)

No revisions yet.