Zadanie z maina

0

Mój problem polega na błędnych odpowiedziach w zadaniu:
https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/ran/

Rozwiązanie brutowe w którym przeglądam każdą możliwość działało poprawnie natomiast po próbie optymalizacji prawie wszędzie otrzymuję wiadomość Zły napis.
Poniżej podaję kod programu

#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>

using namespace std;

struct CMP
{
    bool operator()(const pair<string,int> & p1, const pair<string,int> & p2)
    {
        if(p1.second < p2.second)
            return true;
        else
            return false;
    }
};

int main(int argc, const char * argv[]) {
    
    int n,val;
    cin >> n >> val;
    
    vector<pair<string,int>> data(n);
    
    for(int i = 0; i < n; i++)
        cin >> data[i].first >> data[i].second;
    
    sort(data.begin(), data.end(), CMP());
    
    int pointer = n-1;
    for(int i = 1; i < n; i++)//szuka pary
        if(data[0].second + data[i].second == val)
        {
            cout << data[0].first << " " << data[i].first << endl;
            return 0;
        }
    else if(data[0].second + data[i].second > val)//para data[0] + data[i] > val => zaposz górne ograniczenie(przechowuj jego indeks w zmiennej pointer)
        pointer = i-1;
    
    for(int i = 0; i <= pointer; i++)//szukaj pary dla elementu o indeksie pointer
        if(data[i].second + data[pointer].second == val)
        {
            cout << data[pointer].first << " " << data[i].first << endl;
            return 0;
        }
    
    cout << "NIE" << endl;
    
    return 0;
}


0

Wydaje mi się, że mój błąd polega na tym, że nie koniecznie jest tak, że to "górne ograniczenie" (element o indeksie pointer) będzie tym elementem do pary i może to być jakiś mniejszy, ale nie mogę znaleźć przykładu, który by to potwierdził.

0

Skoro s jest zawsze nieparzyste, to dla przyśpieszenia zrób 2 kontenery, dla parzystych i nieparzystych. jeden z nich sortujesz, i szukasz w nim binarnie s minus kolejna liczba z tego nieposortowanego. Jak jest takowa to masz zwycięzców.

0
sig napisał(a):

Skoro s jest zawsze nieparzyste, to dla przyśpieszenia zrób 2 kontenery, dla parzystych i nieparzystych. jeden z nich sortujesz, i szukasz w nim binarnie s minus kolejna liczba z tego nieposortowanego. Jak jest takowa to masz zwycięzców.

Faktycznie nie wpadłbym na to :D

1 użytkowników online, w tym zalogowanych: 0, gości: 1