Zadanie Radiotelegraf Obóz Ilocamp

Question

Czesc, Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/qvxnxJ6uxu1x9LjRPVyOYtbY/site/?key=statement

Wydaje mi, się że mój pomysł jest dobry, ale się wywala (błędne odpowiedzi) dostaję jedynie 30pkt.

Naliczam sobie na mapie wystapienia(idx-y) danej wartosci i dla kazdej ide sobie gasienica. Tylko nie wiem gdzie jest błąd. Ma ktoś pomysł?

Treść jest trochę dziwnie sformułowana, więc może się upewnie czy ją dobrze zrozumiałem. Mianowicie: szukamy spojnego fragmentu o najwiekszej dlugosci, gdzie mamy maklsymalnie W innych wartosci niż ten kto występuje najwięcej razy.

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int n = 0, w = 0, wczytana_liczba = 0, wyn = 0, lewy_wsk = 0, prawy_wsk = 0, w_gasienicy = 0;
unordered_map<int,vector<int>> stat;

inline void przesuwaj_lewy(auto it)
{
    w_gasienicy -= it->second[prawy_wsk] - it->second[lewy_wsk] - 1;
    lewy_wsk++;
    if (lewy_wsk > prawy_wsk)
    {
        prawy_wsk = lewy_wsk;
        w_gasienicy = 0;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> w;
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        stat[wczytana_liczba].push_back(i);
    }

    for (auto it = stat.begin(); it != stat.end(); ++it)
    {
        lewy_wsk = 0;
        prawy_wsk = 0;
        w_gasienicy = 0;
        while(true)
        {
            wyn = max(wyn,it->second[prawy_wsk] - it->second[lewy_wsk] + 1 + min(w - w_gasienicy,(n-1-it->second[prawy_wsk]) + it->second[lewy_wsk]));
            if (lewy_wsk == prawy_wsk && prawy_wsk == it->second.size() - 1)
                break;
            else if (prawy_wsk == it->second.size() - 1)
                przesuwaj_lewy(it);
            else if (w_gasienicy + (it->second[prawy_wsk+1] - it->second[prawy_wsk] - 1) <= w)
            {
                w_gasienicy += (it->second[prawy_wsk+1] - it->second[prawy_wsk] - 1);
                prawy_wsk++;
            }
            else
                przesuwaj_lewy(it);
        }
    }

    cout << wyn << '\n';

    return 0;
}

Z góry dziękuję za pomoc i poświęcony czas!

Comments

btw. Wiem, że można zrobić w O(N * lg N * lg N) - długość szukamy binarnie i dla danej długości x idziemy z setem i tak bierzemy maxa, ale po 1 to będzie za wolne, dla N <= 10^6 oraz ten mój pomysł z gąsienica wydaje się dobry.

---

Nie wiem gdzie jest błąd w kodzie, ale spojrzałem jak to miałem zrobione i ja korzystałem jednak z bin searcha

---

A jak w czasie liniowym sprawdales czy istnieje fragment długości x? Bo ja wymyśliłem jak to zrobić z setem/kolejka priorytetowa, ale nie wiem jak w czasie liniowym.

---

Słowo klucz: kompresja. Nam przecież wcale nie potrzeba żeby wartości były z zakesu -1e9 do 1e9

---

aaaaaaaaaaaaa,

1 - Wrzcuce wartosci na strukture wartosc, idx

2 - Posortuje po wartosciach

3 - Dla kazdej wartosci wyszukam binarnie jest idx i to będzie jej wartośc i starczy vector zamiast mapy.

dzięki :)

---

@Whistleroosh, Jaka kompresja? Jak? Czemu nie potrzebujemy liczb z zakresu -1e9 do 1e9

---

Obchodzi nas tylko to czy dwie liczby są takie same czy nie. Więc jeśli mamy np. liczby -100, 1, 1e9, -100 to możemy zrobić mapowanie -100 -> 0, 1 -> 1, 1e9 -> 2 czyli dostajemy 0, 1, 2, 0. Wciąż jesteśmy w stanie stwierdzić, ze pierwsza i ostatnia liczba są takie same, a same liczby są już z dużo mniejszego przedziału a nie [-1e9, 1e9]