Takie mam zadnie:
https://szkopul.edu.pl/c/oboz10-14grupa2/p/akc/
niby bardzo proste a połowy testów mi nie zalicza - limit czasu:
#include <iostream>
#include <map>
using namespace std;
map<int, int>mapa;
void LoadujCzasteczki()
{
int count;
cin>> count;
for(int i = 0; i< count; i++)
{
int id;
cin >> id;
mapa[id]++;
}
}
void WypiszWyniki()
{
int count;
cin>> count;
for(int i = 0; i< count; i++)
{
int pytanie;
cin >> pytanie;
cout << mapa[pytanie] << '\n';
}
}
int main()
{
ios::sync_with_stdio(0);
LoadujCzasteczki();
WypiszWyniki();
return 0;
}
więc zrobiłem to co pisało żeby zrobić czyli wyszukiwanie binarne
#include <iostream>
#include <vector>
#include <map>
using namespace std;
struct Czasteczka
{
public:
int rodzaj;
int count;
Czasteczka(int rodzaj, int count)
{
this->rodzaj =rodzaj;
this->count = count;
}
};
vector<Czasteczka> tab;
void LoadujCzasteczki()
{
int count;
cin>> count;
int poprzedniNr = -1000000001;
for(int i = 0; i< count; i++)
{
int id;
cin >> id;
if(poprzedniNr == id)
tab[tab.size()-1].count++;
else
{
poprzedniNr = id;
tab.push_back(Czasteczka(id, 1));
}
}
}
int GetCount(int wartosc, int odileSzukac = -1, int doileSzukac = -1)
{
if(odileSzukac == -1)
odileSzukac = 0;
if(doileSzukac == -1)
doileSzukac = tab.size()-1;
while(true)
{
int polowa = (doileSzukac - odileSzukac + 1) / 2;
if(tab[polowa].rodzaj == wartosc)
return tab[polowa].count;
else if(doileSzukac == odileSzukac) /// jezeli nie jest to ta wartosc to zwarca 0
return 0;
else
{
if(tab[polowa].rodzaj < wartosc)
{
odileSzukac = polowa+1;
}
else
{
doileSzukac = polowa -1;
}
}
}
}
void WypiszWyniki()
{
int count;
cin>> count;
for(int i = 0; i< count; i++)
{
int pytanie;
cin >> pytanie;
cout << GetCount(pytanie) << '\n';
}
}
int main()
{
ios::sync_with_stdio(0);
LoadujCzasteczki();
WypiszWyniki();
return 0;
}
i jest jeszcze wolniej - żadnego testu nie przechodzi :(