• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Radiotelegraf Obóz Ilocamp

Object Storage Arubacloud
0 głosów
327 wizyt
pytanie zadane 7 lutego 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

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!

komentarz 7 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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.
komentarz 7 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
Nie wiem gdzie jest błąd w kodzie, ale spojrzałem jak to miałem zrobione i ja korzystałem jednak z bin searcha
komentarz 7 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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.
1
komentarz 7 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
Słowo klucz: kompresja. Nam przecież wcale nie potrzeba żeby wartości były z zakesu -1e9 do 1e9
komentarz 7 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
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 :)
komentarz 22 października 2023 przez Wojo772233 Początkujący (420 p.)

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

komentarz 22 października 2023 przez Whistleroosh Maniak (56,980 p.)
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]

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 355 wizyt
0 głosów
1 odpowiedź 129 wizyt

92,687 zapytań

141,599 odpowiedzi

320,089 komentarzy

62,048 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...