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

XXX OI - Zadanie Pociąg towarowy

VPS Starter Arubacloud
0 głosów
42 wizyt
pytanie zadane 8 lipca w C i C++ przez Szyszka Gaduła (3,510 p.)
edycja 8 lipca przez Szyszka

Witam,
Zadanie: https://szkopul.edu.pl/problemset/problem/U5dJG9pa-TT5cl-5Fkf8SrwB/statement/
Oto mój pomysł: przechodząc wszystkie elementy listy zawierającej wagony zanotowane przez Bajtka, dla każdego sprawdzam następujące warunki: Czy Bitek kiedykolwiek również zanotował taki wagon? Jeśli tak, to czy index wagonu Bajtka jest większy lub równy indexowi znalezionemu w notatkach Bitka (jeśli jest mniejszy, oznaczałoby to, że Bitek dopisał coś dodatkowo), oraz, jeśli ten warunek jest spełniony, to sprawdzam jeszcze, czy wagon o index + 1 znaleziony u Bitka jest gdzieś po prawo od elementu obecnie przeglądanego w liście Bajtka.

Uznałem, że jeśli wszystkie te warunki są spełnione, to wagon może być zanotowany przez Bitka. Jeśli dowolny z warunków spełniony nie jest, to nie może. Zaimplementowałem to z użyciem binary searcha:
 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool val_exists(const vector<pair<int, int>>& bajtek_val_sorted, int val, int min_idx) {
	if (val == -1) {
		return true;
	}

	if (min_idx == bajtek_val_sorted.size())
		return false;

	int l = 0;
	int r = bajtek_val_sorted.size() - 1;

	while (l <= r) {
		int mid = (l + r) / 2;

		if (bajtek_val_sorted[mid].first == val) {
			if (bajtek_val_sorted[mid].second >= min_idx)
				return true;

			l = mid + 1;
		}
		else if (bajtek_val_sorted[mid].first < val) {
			l = mid + 1;
		}
		else {
			r = mid - 1;
		}
	}

	return false;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	std::cout.tie(nullptr);

	int n, m, k;
	cin >> n >> m >> k;

	// val, original index
	vector<pair<int, int>> bajtek_val_sorted(n);
	vector<pair<int, int>> bitek_val_sorted(m);

	vector<int> bitek(m);

	for (int i = 0; i < n; ++i) {
		cin >> bajtek_val_sorted[i].first;
		bajtek_val_sorted[i].second = i;
	}

	for (int i = 0; i < m; ++i) {
		cin >> bitek_val_sorted[i].first;
		bitek_val_sorted[i].second = i;

		bitek[i] = bitek_val_sorted[i].first;
	}

	sort(bajtek_val_sorted.begin(), bajtek_val_sorted.end());
	sort(bitek_val_sorted.begin(), bitek_val_sorted.end());

	vector<int> result(n);
	for (const pair<int, int>& b : bajtek_val_sorted) {
		int val = b.first;
		int idx = b.second;

		int l = 0;
		int r = m - 1;
		bool valid = false;
		while (l <= r) {
			int mid = (l + r) / 2;

			if (bitek_val_sorted[mid].first == val) {
				int rngbr_idx = bitek_val_sorted[mid].second + 1;
				if (bitek_val_sorted[mid].second <= idx && val_exists(bajtek_val_sorted, (rngbr_idx < bitek.size() ? bitek[rngbr_idx] : -1), idx + 1)) {
					valid = true;
					break;
				}

				r = mid - 1;
			}
			else if (bitek_val_sorted[mid].first < val) {
				l = mid + 1;
			}
			else {
				r = mid - 1;
			}
		}

		result[idx] = valid;
	}

	for (int i = 0; i < n; ++i)
		std::cout << result[i] << ' ';
}

No i cóż. Zadziałało dla testu 3, gdzie każdy rodzaj wagonu występuje maksymalnie 1 raz (czyli w sumie 15pkt). Zły jest pomysł, czy kod?

EDIT: Ponieważ kiedy każy wagon jest unikatowy, to jeśli sprawdzimy jednego z sąsiadów (lewy lub prawy), w moim przypadku wybrałem prawego, i on się zgadza, to mamy pewność, że znaleźliśmy dobre miejsce. Jeśli wagony nie są unikatowe, powinniśmy sprawdzić nie tylko sąsiadów po obu stronach, ale tak na prawdę przejrzeć całą listę Bitka na prawo i na lewo. Czyli potencjalnie O(N*M*logM). Jak to optymalnie rozwiązać?

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

Podobne pytania

0 głosów
1 odpowiedź 163 wizyt
pytanie zadane 10 lipca 2022 w C i C++ przez Latarnik Użytkownik (650 p.)
0 głosów
1 odpowiedź 265 wizyt
pytanie zadane 30 maja 2023 w C i C++ przez Szyszka Gaduła (3,510 p.)
+1 głos
2 odpowiedzi 531 wizyt
pytanie zadane 24 czerwca 2023 w C i C++ przez Szyszka Gaduła (3,510 p.)

92,843 zapytań

141,784 odpowiedzi

320,859 komentarzy

62,177 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.

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...