#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<int,vector<int>> map;//mapa ma mieć liczby np. 1,2,3 i w wektorze zapisuje ich indeksy
int tab[1000*1000+5]; //tablica ma przechowywać zapytania
int bs(int current,int index){
int l = 0,r = map[current].size()-1;
int ans = -1;
while(l <= r){
int mid = l + (r - l + 1) / 2;
if(map[current][mid] < index)
l = mid + 1;
else if(map[current][mid] > index)
{
ans = mid;
r = mid - 1;
}
else if(map[current][mid] == index)
l = mid + 1;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
//map[1]->indeksy_gdzie_jest
for(int i=0;i<n;++i){
int x;
cin >> x;
map[x].push_back(i);
}
//test_cases
int t;
cin >> t;
for(int j=0;j<t;++j){
int k;
cin >> k;
bool notok = false;
int index = 0;
//wrzucam całą listę zapytania do tablicy
for(int l=0;l<k;++l){
cin >> tab[l];
}
for(int i=0;i<k;++i){
//biorę aktualną liczbę z zapytania
int current = tab[i];
int answer;
//sprawdzam czy nie ma tam elementu
if(map.find(current) == map.end())
{ notok = true;break;}
//sprawdzam czy element występuje raz
if(map[current].size() == 1)
answer = 0;
else
answer = bs(current,index);
//jeśli nie ma
if(answer == -1 || map[current][answer] < index)
{
notok = true;
break;
}
index = map[current][answer];
}
if(notok == false)
cout << "TAK" << '\n';
else
cout << "NIE" << '\n';
}
return 0;
}
Witam, rozwiązuję zadanie : https://szkopul.edu.pl/problemset/problem/Ak4wWPkNtHpF-OiulN1gixfW/site/?key=statement. Wchodzi na 80 pkt, nie przechodzi dwóch przypadków. Czy wie ktoś może co mogłem przeoczyć? Z góry dziękuję za poświęcony czas.
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
unordered_map<int,vector<int>> map;
int tab[1000*1000+5];
int bs(int current,int index){
int l = 0,r = map[current].size()-1;
int ans = -1;
while(l <= r){
int mid = l + (r - l + 1) / 2;
if(map[current][mid] < index)
l = mid + 1;
else if(map[current][mid] > index)
{
ans = mid;
r = mid - 1;
}
else if(map[current][mid] == index)
l = mid + 1;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
for(int i=0;i<n;++i){
int x;
cin >> x;
map[x].push_back(i);
}
int t;
cin >> t;
for(int j=0;j<t;++j){
int k;
cin >> k;
bool notok = false;
int index = 0;
for(int l=0;l<k;++l){
cin >> tab[l];
}
for(int i=0;i<k;++i){
int current = tab[i];
int answer;
if(map.find(current) == map.end())
{ notok = true;break;}
if(map[current].size() == 1)
answer = 0;
else
answer = bs(current,index);
if(answer == -1 || map[current][answer] < index)
{
notok = true;
break;
}
index = map[current][answer];
}
if(notok == false)
cout << "TAK" << '\n';
else
cout << "NIE" << '\n';
}
return 0;
}