Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #58 da revista programar. Faz já o download aqui!

epolozero

[Resolvido] problema das olimpiadas, Invalid Funtion

Mensagens Recomendadas

epolozero    14
epolozero

Boas, estou a resolver um problema das olimpiadas ( http://www.dcc.fc.up.pt/oni/problemas/2014/qualificacao/probA.html ) mas esta a dar-me 88 pontos com invalid function, Resolvi o problema com o conceito de buckets (acho...).

#include <stdio.h>


#define MAX_VALUE 1000000
#define MAX_BUCKET 1000 //sqrt(max_value)
unsigned long values[MAX_VALUE] = {0};
unsigned long bucket[MAX_VALUE];
unsigned long sum[MAX_BUCKET] = {0};


int main(void){

  unsigned long n, k, i, j, l, cnt;
 char op[4];

  scanf("%lu", &n);

  //buckets
  for (i=0, j=0; i< MAX_VALUE; i++, j = i / MAX_BUCKET){
	  bucket[i] = j;
  }


  while(n--){
	  scanf("%s", op);
	  scanf("%lu", &k);
	  switch(op[0]){

			 //inserir
			 case 'I':
					values[--k]++;
					sum[bucket[k]]++;
					break;

			 //remover
			 case 'R':
					values[--k]--;
					sum[bucket[k]]--;
					break;

			 //k-esima melhor carta
			 case 'P':
					for (i=MAX_BUCKET-1, j=0; i>=0; i--){
					   j += sum[i];
					   if (j >= k){
							  for (  l = (i + 1) * MAX_BUCKET - 1 , cnt = j - sum[i] ; ; l--){
									 cnt += values[l];
									 if (cnt >= k){
											printf("%lu\n", l+1);
											break;
									 }
							  }
							  break;
					   }
					}
					  break;
	  }
  }

  return 0;
}



Queria que alguem me dissesse o que tenho que melhorar, ou o que estou a fazer errado.

Editado por epolozero

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade