Zadanie "Test Na Inteligencję" OI XVII

Question

#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;
}

 

Comments

Uhh ogólnie niezbyt rozumiem co robisz, potężnie tutaj przekombinowałeś. Do pytania typu "czy z `1 5 4 5 7 8 6` da się zrobić `1 5 5 8 6`" nie potrzebujesz unordered_map, nie potrzebujesz binary searchów :)

Tak na intuicję to Twój kod potencjalnie pogubi się z przypadkami typu `5 5` -> `5 5`, `5 5` -> `5 5 5`?

---

właśnie problem taki, że niestety trzeba bin searcha / seta, bo zapytań dużo i O(N*Q) nie przejdzie raczej

---

Ale warte uwagi, jest, że jak się robi to na secie, to wystarcza proste S.lower_bound()

---

Jakby co, właśnie zrobiłem bez binary searcha z 100/100 (choć niektóre testy na styk wyszły), jedyne co to unordered_set - więc się da :) Ale OK, rozumiem czemu takie rozwiązanie też zadziała.

W każdym razie w tym powyższym tak jak mówiłem, na oko (przynajmniej jednym) problemem było nie inkrementowanie indeksu po znalezionej liczbie.

---

Przy tym pomyślę, co ja i Dani zrobiliśmy, musimy szybko umiec znaleźć pierwsze wystąpienie danej wartości > x, można to zrealizować bin searchem, albo tak jak ty zapewne zrobiłeś setem/unordered_set em. Trzeba tylko pamiętać, że set zazwyczaj może działać wolniej niż bin search, bo ma stosunkowo duża stałą. Ale oczywiscie też ma operacje w logu.