Niestety, każde z nich przekracza limit czasu. Pierwsze jest oparte na sortowaniu i wyszukiwaniu binarnym. Drugie na sortowaniu, wyszukiwaniu binarnym i coś na wzór hash_mapy.
1:
Kod: Zaznacz cały
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void wczytaj(vector<int> &b);
int main()
{
int n,m;
cin>>n>>m;
vector<int> wag1(n);
vector<int> wag2(n);
vector<int> zapytania(m);
vector<string> odp;
wczytaj(wag1);
wczytaj(wag2);
wczytaj(zapytania);
sort(wag2.begin(),wag2.end());
sort(wag1.begin(),wag1.end());
for(int i=0;i<m;i++)
{
for(int k=0;k<n;k++)
{
int szukane=zapytania[i]-wag1[k];
int szukane2=zapytania[i]-wag2[k];
if(szukane<=0 || szukane2<=0)
{
odp.push_back("NIE");
break;
}
bool exist=binary_search(wag2.begin(),wag2.end(),szukane);
bool exist2=binary_search(wag1.begin(),wag1.end(),szukane2);
if(exist || exist2)
{
odp.push_back("TAK");
break;
}
else if((!exist || !exist2) && k==n-1)
{
odp.push_back("NIE");
}
}
}
for(int i=0;i<odp.size();i++)
{
cout<<odp[i]<<endl;
}
}
void wczytaj(vector<int> &b)
{
for(int i=0;i<b.size();i++)
{
int liczba;
cin>>liczba;
b[i]=liczba;
}
}
2:
Kod: Zaznacz cały
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;
void wczytaj(vector<int> &b);
void wczytaj2(int a,vector<int> &b);
int main()
{
int n,m;
cin>>n>>m;
vector<int> wag1(n);
vector<int> wag2(100000000);
vector<int> zapytania(m);
vector<string> odp;
wczytaj(wag1);
wczytaj2(n,wag2);
wczytaj(zapytania);
sort(wag1.begin(),wag1.end());
for(int i=0;i<m;i++)
{
for(int k=0;k<n;k++)
{
//szukane-liczba z wa2 taka, że wag1+wag2=szukane
int szukane=zapytania[i]-wag1[k];
if(szukane<=0)
{
odp.push_back("NIE");
break;
}
if(wag2[szukane-1]==szukane)
{
odp.push_back("TAK");
break;
}
else if(wag2[szukane-1]!=szukane && k==n-1)
{
odp.push_back("NIE");
}
}
}
for(int i=0;i<odp.size();i++)
{
cout<<odp[i]<<endl;
}
}
void wczytaj(vector<int> &b)
{
for(int i=0;i<b.size();i++)
{
int liczba;
cin>>liczba;
b[i]=liczba;
}
}
//tworzy cos na wzor hash mapy czyli licza=5, leci do komorki o nr 4(bo liczymy indeksy od 0)
void wczytaj2(int a, vector<int> &b)
{
for(int i=0;i<a;i++)
{
int liczba;
cin>>liczba;
b[liczba-1]=liczba;
}
}