Jak przyspieszyć program

Witam,

mam takie zadanie:
http://solve.edu.pl/contests/download_desc/1924

i taki kod

#include <iostream>
using namespace std;
long long int tab1[500005]={0};
long long int tab2[500005]={0};

int main()
{
    std::ios_base::sync_with_stdio (false);
  cin.tie (0);
  cout.tie (0);
  
    long long int n=0,q=0,p=0,p2=0,i=1;
    cin>>n>>q;
    long long int ile=n;
    while (n--)
    {
        cin>>tab1[p];
        p++;
    }
    while (q--)
    {
        cin>>tab2[p2];
        p2++;
    }
    n=-1;
    while(p2>0)
    {
        n++;
        q=0;
        p=ile;
        while((p>0)&&(q<ile))
        {
            if(tab2[n]==tab1[q])
            {
                cout<<q+1<<"\n";
                goto dalej;
            }
            q++;
            p--;
        }
        cout<<"NIE"<<"\n";
        dalej:
        p2--;
    }
    return 0;
}

Dziala dobrze ale wolno:-(
Na trzech testach przekracza mi limit czasu :-(
Ktoś może poradzić co zmienić ?

Zbuduj hashmapę wartość⟶pierwsze wystąpienie a potem w niej wyszukuj. Na razie masz wyszukiwanie O(n). Interesuje Cię std::unordered_map

Możesz opisać, jak działa Twój algorytm?

EDIT: Albo najpierw Zrób jak powyżej, gdy dalej będzie za wolno, to się zobaczy.

kq napisał(a):

Zbuduj hashmapę wartość⟶pierwsze wystąpienie a potem w niej wyszukuj. Na razie masz wyszukiwanie O(n). Interesuje Cię std::unordered_map

A bez hashmapy? Nie wiem nawet co to

Ja zamiast std::unordered_map użyłbym tablicy int itemsPos[1000000] (to tylko 4MB). Więcej dużych danych nie potrzeba.

Cześć,

mam taki kod ale znowu coś nie działa :-(

#include <iostream>
#include <sstream>
#include <map>
using namespace std;
int tab1[500002];
int tab2[500002];
map<int, string> znalezioneWczesniej;
map<int, string>::iterator it;

string getStringFromInt(int a);

int main()
{
    std::ios_base::sync_with_stdio (false);
	cin.tie (0);
	cout.tie (0);
	int nSize=0,qSize=0;
	cin>>nSize>>qSize;
	for(int i = 0; i < nSize; ++i)
	{
		cin>>tab1[i];
	}

	for(int i = 0; i < qSize; ++i)
	{
		cin>>tab2[i];
	}

	for( int i = 0; i < qSize; ++i)
	{
		// sprawdz czy juz znalezione
		it = znalezioneWczesniej.find(tab2[i]);
		if( it != znalezioneWczesniej.end())
		{
			cout << znalezioneWczesniej[i] << endl;
		}
		else // jeszcze nie bylo tego
		{
			int j = 0;
			for(; j < nSize; ++j)
			{
				if( tab1[j] == tab2[i] )
				{
					string str = getStringFromInt(j+1);
					cout<<str<<endl;
					znalezioneWczesniej[tab2[i]] = str;
					break;
				}
			}
			if ( j == nSize )
			{
				string str("NIE");
				cout<<str<<endl;
				znalezioneWczesniej[tab2[i]] = str;
			}
		}
	}
}

string getStringFromInt(int a)
{
	stringstream ss;
	ss << a;
	return ss.str();
}

mam taki kod ale znowu coś nie działa :-(

to napraw to cos to bedzie dzialac ;)

my nie wiemy co to jest to cos

fasadin napisał(a):

mam taki kod ale znowu coś nie działa :-(

to napraw to cos to bedzie dzialac ;)

my nie wiemy co to jest to cos

:-)

W testach pokazuje mi:

cia0a.in 0.00 s / 0.50 s 5.17 MB OK
cia0b.in 0.00 s / 0.50 s 5.17 MB OK -
cia1a.in 0.00 s / 0.50 s 5.17 MB OK
cia1b.in 0.00 s / 0.50 s 5.17 MB Błędna odpowiedź -
cia2.in 0.00 s / 0.50 s 5.17 MB Błędna odpowiedź -
cia3.in 0.00 s / 0.50 s 5.17 MB Błędna odpowiedź -
cia4.in 0.07 s / 1.00 s 5.55 MB Błędna odpowiedź -
cia5.in 1.47 s / 2.00 s 6.68 MB Błędna odpowiedź -
cia6.in 3.00 s / 3.00 s 6.06 MB Limit czasu przekroczony -
cia7.in 6.00 s / 6.00 s 5.68 MB Limit czasu przekroczony -

weź ten kod podziel na funkcje, tak żebyśmy nie widzieli jednego wielkiego krzaczka.
Może ci się wtedy samo naprawi.

Poza tym, podpowiedzi jakie dostałeś powinny cię nakierować na rozwiązanie, gdzie NIE MA zagnieżdżonych pętli for, a ja u ciebie coś takiego widzę.

Dziękuję za pomoc. Ostatecznie taki mam kod:

#include<iostream>
using namespace std;
int tab1[1000005];
int main()
{
	int n, q,a,b;
	cin>>n>>q;
	for (int i=0; i<n;i++ )
	{
		cin>>b;
		if (tab1[b]==0)
		{
			tab1[b]=i+1;
		}
	}
	for (int i=0; i<q; i++)
	{
		cin>>a;
		if(tab1[a]==0)
		{
			cout <<"NIE"<<"\n";
		}
		else
		{
			cout<< tab1[a]<<"\n";
		}
	}
	return 0;
}