TOPIC

PROBLEM 1424 - URI Fórum 1.0

beecrowd asked on Jun 3 2013

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • andresroliveira replied 8 years ago

    OOO gente, eu to tomando RE ou WA100% (varia se eu mudo uma coisinha ou outra) :\

    alguem pode me ajudar?

    #include <bits/stdc++.h>
#define N 100010
#define LL long long int

using namespace std;

vector < vector < LL > > A ;

LL n,m,k,v,a,i,j,s;

int main(){
    while(~scanf("%lld%lld",&n,&m)){
        A.clear();

        for(i=0;i<n;i++){
            cin >> s;

            a = 1;

            while(A[s][a]) a++;

            A[s][a] = i+1;
        }

        for(i=0;i<m;i++){
            scanf("%lld%lld",&k,&v);

            cout << A[v][k] << '\n';
        }
    }
    return 0;
}

  • mmelo3 replied 8 years ago

    Seu código falha no seguinte caso:

    3 3
1 2 3
1 1
1 2
1 3
3 3
1 2 3
2 2
2 3
2 1

    Ele imprime:

    1
2
3
2
3
1

    Mas o correto seria:

    1
2
3
0
0
0

  • dcpietropaolo replied 8 years ago 

    #include <bits/stdc++.h>
using namespace std;
int main (){
   int a, b, c, d, e, f, g, k, r;
   vector < int > v;
   map <int , vector <int> > m;
   map <int , vector <int> > :: iterator it;

    while (scanf ("%d %d", &a, &g)!=EOF){
   f=1;
   while (a--){
      scanf ("%d", &c);
      if (m.count (c) ){
         m[c].pop_back();
         m[c].push_back (f);
         m[c].push_back (-1);
      }
      else {
         v.push_back (f);
         v.push_back (-1);            
         m.insert ( pair <int, vector <int> > (c, v));
         v.clear();
      }
      f++;
   }

   while (g--){
      r=1;
      scanf ("%d %d", &e, &d);
      if ( m.count (d)){
         k=0;
         while (e--){

            if (m[d][k]==-1) break;
            if (e==0){
            printf ("%d\n",   m[d][k]);
            r=0;            
            }            
            k++;

         }
      }
      if (r==1) {
         printf ("0\n");
      }
   }
}
}

    WA 10% ainda :-;

  • mmelo3 replied 8 years ago

    A entrada contém vários casos de teste, mas você só está lendo um.

  • dcpietropaolo replied 8 years ago 

    #include <bits/stdc++.h>
using namespace std;
int main (){
    int a, b, c, d, e, f, g, k, r;
    vector < int > v;
    map <int , vector <int> > m;
    map <int , vector <int> > :: iterator it;
    scanf ("%d %d", &a, &g);
    f=1;
    while (a--){
        scanf ("%d", &c);
        if (m.count (c) ){
            m[c].pop_back();
            m[c].push_back (f);
            m[c].push_back (-1);
        }
        else {
            v.push_back (f);
            v.push_back (-1);               
            m.insert ( pair <int, vector <int> > (c, v));
            v.clear();
        }
        f++;
    }

    while (g--){
        r=1;
        scanf ("%d %d", &e, &d);
        if ( m.count (d)){
            k=0;
            while (e--){

                if (m[d][k]==-1) break;
                if (e==0){
                printf ("%d\n", m[d][k]);
                r=0;                
                }               
                k++;

            }
        }
        if (r==1) {
            printf ("0\n");
        }
    }
}

    WA 100%

  • mmelo3 replied 8 years ago

    Uma ideia para resolver essa questão seria criar um mapa de inteiros associados a um vetor. Assim, cada vez que o número aparece na entrada, coloca-se a posição em que ele apareceu no vetor.

  • pyanderson replied 9 years ago

    Probably, the test cases are broader. Ever happened to me a couple times, so I tried to solve the problem differently.

  • arahman5 replied 9 years ago

    This problem is also in UVA and my code is accepted there. But here (URI) 10% wrong answer???? Why???

  • dcpietropaolo replied 9 years ago 

    #include <stdio.h>
#include <string>
#include <iostream>
#include <map>
using namespace std;
int main (){
    int a, b, c, aux, e, d, aux2, cont, vd;
    map <int, int> m;
    map <int, int>::iterator it;
    while (scanf ("%d %d", &a, &b)!=EOF){
        for (c=0; c<a; c++){
                scanf ("%d", &aux);
                m.insert(pair<int, int> (c, aux));
        }
            for (aux2=0; aux2<b; aux2++){
                scanf ("%d %d", &e, &d);
                cont=0;
                vd=1;
                for (it= m.begin(); it != m.end(); it++){
                    if (it->second==d){
                        cont++;
                        }
                    if(cont==e){
                        vd++;
                        printf ("%d\n", it->first+1);
                        break;
                        }
                }
                if (vd==1){
                    puts("0");
                    }
        }
    }

}

    TLE

  • gugabribeiro replied 9 years ago

    Não dá para criar uma matriz com tantas posições como você está tentando fazer.

  • dcpietropaolo replied 9 years ago 

    #include <stdio.h>

int main (){
    unsigned long long int a, s, d, f, u, x, g, h[1000001], k[1000000][100000];
    while (scanf ("%d %d", &a, &s)!=EOF){
        for (g=0; g<100000; g++){
            for (u=0; u<1000000; u++){
                k[u][g]=0;
                }
            }
        for (g=0; g<a; g++){
                scanf ("%d", &h[g]);
                k[h[g]][g]=k[h[g]][g]++;

        }

        for (g=0; g<s; g++){
            int vdd=1;
            scanf ("%d %d", &x, &u);
            int cont=0;
            for (int au=0; au<1000000; au++){
                    if (k[u][au]!=0){
                        cont++;
                        }
                        if(cont==x){
                            printf ("%d\n", au+1);
                            vdd=0;
                            break;
                            }
                                }
            if (vdd==1){
                printf("0\n");
            }
        }

    }

}

    Compilation anteriormente com tamanho do vetor menor deu runtime;

  • crussi replied 9 years ago

    Você está no caminho certo, é isso mesmo! Quanto ao vetor de 10^6 pode-se criar sim.

  • aaabotaleb replied 9 years ago

    Então, eu até tinha pensado isso, mas minha preocupação é o tamanho ocupado. Não consigo imaginar uma resolução em que a criação de um vetor (de um tipo de dado qualquer, maior ou igual a um int) de 1.000.000 de posições não seja necessária. Posso estar enganado mas isso levará a um Runtime Error, não? Ou posso, sim, criar um vetor dessa magnitude?

    Talvez um vetor dinâmico em que a posição de um número só tem memória alocada caso ele seja encontrado? E esse vetor seria de uma estrutura em que cada posição teria sua própria lista encadeada, e cada "nó" indicaria um índice em que ele foi encontrado?

  • crussi replied 9 years ago

    E se você armazenasse o índice das ocorrências desse número? Veja que você pode ter a quantidade do número requerido como um bônus e a complexidade seria bem menor.

  • aaabotaleb replied 9 years ago

    Alguém tem alguma dica? Tentei ir checando um elemento por vez e, já esperando, tomei TLE. Tinha pensado em criar um vetor apenas pra indicar se a quantidade do número requerido é suficiente... para economizar tempo; porém, não acho que um vetor de 1.000.000 de posições (o índice se referiria ao número) será suportado.

    No mais, obrigado!

  • crussi replied 9 years ago

    Apesar de apresentar W.A. o problema está no tamanho do vetor hash = new lista[1000002]; Fiz alguns testes diminuindo esse valor e compilou legal. Tente reformular esta parte.

    Espero ter ajudado.

  • blublublu replied 9 years ago

    Meu código ta dando WA,mas todos os toolkits dão certo alguém sabe o que tem errado no meu código ?

    Código Removido!!!

  • yshmelev replied 9 years ago

    Why does it say Time Limit Exceeded? Should i make my algorithm better or the problem is in EOF?

    #include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
    int *array = NULL;
    int size, queries, occurrence, number, count, position, zero = 0;
    bool flag = false;
    while (cin >> size)
    {
        cin >> queries;
        array = new int[size];
        for (int i = 0; i < size; i++)
        {
            cin >> array[i];
        }
        for (int i = 0; i < queries; i++)
        {
            count = 0;
            position = 0;
            flag = false;
            cin >> occurrence >> number;
            for (int j = 0; j < size; j++)
            {
                if (array[j] == number)
                {
                    count++;
                    position = j + 1;
                    if (count == occurrence)
                    {
                        cout << position << "\n";
                        flag = true;
                        break;
                    }
                }
            }
            if (!flag)
            {
                cout << zero << "\n";
            }
        }
        delete[]array;
    }
    return 0;
}

  • jbsilva replied on Jun 15 2013

    Só troquei uma estrutura de dados e ficou muito mais rápido. Aparentemente o problema era mais o tempo de alocação e desalocação de memória do que o 'algoritmo'.

  • NeilorTonin-beecrowd replied on Jun 11 2013

    As entradas foram modificadas para ficar de acordo com a especificação. Ela ficou com 1 MB. A diferença para o UVA é que está testando dentro dos limites (caso de teste com até 100 mil elementos e 100 mil consultas, sendo que cada um destes elementos pode ter um valor entre 1 e 1 milhão.)

    Neste caso, tentativas de resolução com técnica semelhante a count sort deve dar tempo aproximado de 10 segundos, e não passa.

1 of 2