Zadanie
Ako všetci dobre vieme, Marťania náš často navštevujú vo svojich lietajúcich tanieroch. Marťan Denys práve dostal vodičský preukaz. Rozhodol sa ho naplno využiť a priletieť na Slovensko po legendárnu kofolu a horalky (tie na Marse nedostať). To však precenil svoje letecké schopnosti, pretože zabudol na ďalšiu vec, ktorú na Marse nemajú1 – atmosféru. A Denys si to nevedomky namieril rovno do snehovej búrky.
Neostávalo mu nič iné, ako zavolať do KSP2 a oznámiť svoje núdzové pristátie na jednej z ich pristávacích dráh. Tisícky KSPákov na ňu okamžite vybehli v snahe byť prvými, ktorí Denysa privítajú. To však nie je úplne jednoduché – Denysa snehová búrka kotrmáca hore-dolu, a tak síce dokáže technikou Kontrolovaného Samovoľného Pádu zaručiť, že “pristane” na dráhe, nevie však, kde na nej sa nakoniec ocitne.
Každý vedec si teda vybral nejaké miesto na dráhe, na ktoré sa postavil a úzkostlivo čaká, kde Denys nakoniec skončí. Hneď ako pristane, každý z nich sa plnou rýchlosťou rozbehne jeho smerom.
KSP programátorom sa podarilo pomocou simulácie vypočítať niekoľko pravdepodobných miest na dráhe, na ktorých by Denys mohol skončiť. KSPákov teraz pre každé z týchto miest nesmierne zaujíma, kto by sa k Denysovi dostal ako prvý, keby Denys pristál na tomto mieste. KSP potrebuje vašu pomoc!
Úloha
Pristávacia dráha je veľmi dlhá, rovná cesta. Pozíciu každého KSPáka či možného Denysovho pristátia si preto vieme jednoducho vyjadriť vzdialenosťou od jej začiatku v metroch.
Každý KSPák sa postavil na nejaký meter \(x_i\) na pristávacej dráhe a keď Denys pristane, rozbehne sa k nemu rýchlosťou \(v_i\) metrov za sekundu. Pre každú polohu pristátia v zozname zistite, ktorí KSPáci by Denysa privítali ako prví, keby pristál na nej.
Formát vstupu
V prvom riadku vstupu sú dve celé čísla \(n, q\) (\(1 \leq n,q \leq 300\,000\)): počet KSPákov a počet možných miest, na ktorých Denys možno nakoniec pristane. KSPáci sú očíslovaní od \(1\) po \(n\).
Nasleduje \(n\) riadkov, \(i\)-ty z nich obsahuje dve celé čísla \(x_i, v_i\) – začiatočnú polohu a rýchlosť KSPáka číslo \(i\). Dvojice \(x_i, v_i\) sú navzájom rôzne. Platí \(0 \leq x_i < 10^9\) a \(0 < v_i \leq 10^9\).
Nakoniec, v poslednom riadku vstupu je \(q\) medzerou oddelených celých čísel \(y_1, y_2, \dots, y_q\) (\(0 \leq y_j < 10^9\)) – zoznam možných pristávacích miest. Sú navzájom rôzne a žiadne z nich sa nerovná začiatočnej polohe niektorého KSPáka.
Formát výstupu
Vypíšte \(q\) riadkov. V \(j\)-tom z nich vypíšte počet KSPákov, ktorí by Denysa privítali ako prví, keby pristál na \(y_j\)-tom metri pristávacej dráhy – teda počet takých \(i\), pre ktoré \(1 \leq i \leq n\) a zlomok \(\frac{|x_i - y_j|}{v_i}\) je najmenší cez všetky \(i\). Následne do toho istého riadku vypíšte čísla všetkých takýchto KSPákov, zoradené vzostupne.
Hodnotenie
Pre jednotlivé testovacie sady platia nasledovné obmedzenia:
| číslo sady | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) |
|---|---|---|---|---|---|---|---|---|
| \(n,q \leq\) | \(500\) | \(3\,000\) | \(25\,000\) | \(50\,000\) | \(75\,000\) | \(100\,000\) | \(200\,000\) | \(300\,000\) |
Navyše, v sadách \(3,4,5\) platí \(x_i < y_j\) pre všetky zmysluplné \(i, j\) – teda všetci KSPáci stoja naľavo od všetkých možných pristávacích miest.
Príklady
Input:
4 7
10 5
30 1
20 4
100 1
5 31 22 15 85 60 61Output:
1 1
1 2
1 3
1 1
2 1 4
2 1 3
1 1Input:
3 4
10 5
30 1
20 4
31 85 60 61Output:
1 2
1 1
2 1 3
1 1Toto je príklad vstupu v sadách 3,4,5
Stará dobrá hrubá sila
Ako inak – úloha sa dá riešiť aj hrubou silou. Pre každé pristávacie miesto si pamätáme zoznam KSPákov v jeho výsledku a najlepší čas, za ktorý títo KSPáci k nemu pribehnú – na začiatku si tento čas inicializujeme na nekonečno. Potom jednoducho prejdeme celý zoznam KSPákov, keď natrafíme na niekoho s rovnakým časom príchodu ako doterajší najlepší, pridáme si ho do zoznamu, a ak na niekoho s lepším časom, čas si zmeníme naň, zoznam premažeme a pridáme tam len tohto najnovšieho.
Pre každé z \(q\) pristávacích miest prejdeme celý zoznam \(n\) KSPákov, spravíme konštantne veľa operácií a niekdy premažeme doterajší zoznam – do tohto zoznamu však vždy pridáme nanajvýš \(n\) KSPákov, teda pre jedno pristávacie miesto spravíme \(O(n)\) operácií, čiže dokopy dostávame časovú zložitosť \(O(nq)\). Toto postačuje na prvé dve sady, s dostatočne rýchlym jazykom a implementáciou aj na tretiu. Pamätáme si všetkých \(n\) KSPákov a otázky vieme riešiť po jednej, pričom v rámci jej riešenia si pamätáme zoznam dĺžky nanajvýš \(n\), čiže máme pamäťovú zložitosť \(O(n)\).
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,q;
cin >> n >> q;
vector<pair<int,double> > KSPaci(n);
for(int i=0;i<n;++i)
cin >> KSPaci[i].first >> KSPaci[i].second;
while(q--)
{
int y;
cin >> y;
vector<int> odpoved;
double najrychlejsi = 2000000000;
for(int i=0;i<n;++i)
{
double cas = abs(KSPaci[i].first-y)/KSPaci[i].second;
if(cas == najrychlejsi)
odpoved.push_back(i+1);
else if (cas < najrychlejsi)
{
najrychlejsi = cas;
odpoved = {i+1};
}
}
cout << odpoved.size();
for(int KSPak:odpoved)
cout << " " << KSPak;
cout << "\n";
}
return 0;
}Viete povedať, ktorá časť tejto implementácie je ‘pomalá’?
Poznámka o výstupe
Jedna otázka, ktorá vám mohla po prečítaní zadania skrsnúť, je ako veľký môže vlastne byť výstup. Keby totiž skoro každý KSPák mohol mať najlepší čas na skoro každom mieste pristátia, museli by sme vypísať až \(O(nq)\) čísel, čo by sme teda vo väčších sadách nestihli bez ohľadu na to, ako by sme hľadali odpoveď.
Takéto niečo však nemôže nastať vďaka podmienkam v zadaní, to jest pristávacie miesta sú navzájom rôzne, a Denys nikdy nepristane na niektorom KSPákovi, a dvojice \(x_i, v_i\) sú navzájom rôzne. Toto nám vyplynie z pozorovania, ktoré spravíme popri vymýšľaní vzorového riešenia.
Jednosmerné riešenie
Pozrime sa teda na ľahšiu verziu úlohy – naše riešenie musí mať síce oveľa lepšiu časovú zložitosť, nemusíme sa však starať o to, že KSPáci sa ku každému pristátiu hrnú z oboch strán. V momente, keď Denys pristane, všetci KSPáci sa jednoducho rozbehnú doprava ako rýchlo vládzu.
Ak si vypočítame pozíciu každého predbehnutia medzi dvoma KSPákmi, úlohu môžeme riešiť jednoduchým zametacím algoritmom. Postupne pôjdeme po pristávacej dráhe zľava doprava a budeme si pritom udržiavať poradie KSPákov, v akom prejdú cez našu aktuálnu pozíciu. Na začiatku sa nachádzame naľavo od najľavejšieho KSPáka a naše poradie je zatiaľ prázdne (lebo cez našu pozíciu nikdy nijaký KSPák neprejde). Vždy, keď prechádzame cez štartovaciu pozíciu nejakého KSPáka, pridáme si ho do nášho poradia, konkrétne na čelo (keďže na danej pozícii začína, bude tam ako prvý)1. Vždy, keď prejdeme cez pozíciu, kde nejaký KSPák predbehne iného, vymeníme si týchto dvoch KSPákov v našom poradí. Keď prechádzame cez pristávacie miesto, zapíšeme si ako odpoveď KSPáka, ktorý je momentálne prvý v poradí (a v prípade, že sa na tej istej súradnici udejú aj nejaké predbehnutia, zapíšeme sem aj ostatných s rovnakým časom).
Problém je však v tom, že predbehnutí medzi KSPákmi môže byť až \(\frac{n \cdot (n-1)}{2}\), keby boli KSPáci zoradení zľava doprava zostupne podľa rýchlosti. Uvedomme si ale, že drvivá väčšina predbehnutí v skutočnosti vôbec nie je dôležitá. Ak totiž ľubovoľného KSPáka niekto predbehne, môžeme ho už úplne ignorovať – predbehol ho nejaký rýchlejší KSPák, takže už nikdy vo vedení nebude. To znamená, že pri simulácii predbehnutia môžeme namiesto vymenenia dvoch KSPákov v poradí úplne vyhodiť predbehnutého KSPáka z poradia. Pre každého KSPáka tak budeme simulovať iba prvé predbehnutie, keď bol predbehnutý iným KSPákom. A takýchto predbehnutí je nanajvýš \(n\). Tu si všimnime, že okrem KSPáka, ktorý bol sám na čele preteku, sa do odpovede na otázku dostane iný len vtedy, keď práve v tom momente predbehne ešte nepredbehnutého KSPáka. Keďže takýchto predbehnutí je \(O( n)\), celkový počet KSPákov v odpovediach je \(O(n+q)\) (dokonca tesný odhad je práve \(n+q\)).
Teraz však máme problém, že nevieme, kde tieto dôležité predbehnutia nastanú. Nemôžeme si ich len tak vypočítať na začiatku, lebo nevieme, medzi ktorými dvojicami KSPákov nastanú a skúšať všetky dvojice by bolo príliš pomalé. Namiesto toho to budeme robiť postupne. Okrem poradia KSPákov si budeme pamätať ešte zoznam všetkých pozícií, kde niektorý KSPák z nášho poradia predbehne KSPáka, ktorý je momentálne v poradí tesne pred ním. Ak sa nám tento zoznam podarí udržiavať aktuálny, vždy keď bude treba odsimulovať nejaké predbehnutie, toto predbehnutie budeme mať v zozname, teda o ňom budeme vedieť.
Vždy, keď pridávame KSPáka na čelo poradia, vypočítame si pozíciu, kde ho predbehne KSPák, ktorý bol na čele doteraz (ak ho predbehne) a pridáme si ju do zoznamu predbehnutí. Keď simulujeme, že nejaký KSPák \(A\) predbehol KSPáka \(B\), toto predbehnutie vyhodíme zo zoznamu. Okrem toho sa pozrieme, či KSPák \(A\) nepredbehne niekedy neskôr aj KSPáka, ktorý bol doteraz v poradí tesne pred \(B\) (označme ho \(C\)) a ak áno, pridáme si do zoznamu predbehnutí pozíciu, kde ho predbehne. Nakoniec sa ešte pozrieme, či sme v zozname nemali, že \(B\) predbehne \(C\) a ak áno, vymažeme toto predbehnutie zo zoznamu (keďže už nie je aktuálne).
Pozíciu, kde nejaký KSPák \(X\) predbehne KSPáka \(Y\) vypočítame jednoducho ako \(x_{Y} + \frac{x_{Y}-x_{X}}{v_{X}-v_{Y} } \cdot v_{Y}\).
Všimnime si, že so zoznamom predbehnutí manipulujeme, iba keď pridávame KSPáka, alebo keď simulujeme predbehnutie, teda dokopy maximálne \(2n\) krát.
Už si musíme len vybrať vhodné dátové štruktúry. Zoberme si poradie KSPákov. Od neho potrebujeme \(q\) krát pristúpiť k vedúcemu KSPákovi, \(O(n)\) krát pridať KSPáka na začiatok poradia a \(O(n)\) krát vyriešiť predbehnutie, ktoré zahŕňa zmazanie jedného prvku (predbehnutého KSPáka) a nájdenie KSPáka, ktorý sa ocitne tesne pred predbiehajúcim KSPákom. Na túto úlohu sa hodí spájaný zoznam, ktorý všetky tieto operácie dokáže robiť v konštantnom čase.
Ak sa nám však nechce implementovať spájaný zoznam, môžeme namiesto neho použiť usporiadanú množinu, ktorá je v mnohých jazykoch už implementovaná, napríklad set v C++. Prvky pritom budeme usporiadavať podľa štartovacej pozície (keďže v poradí máme iba nepredbehnutých KSPákov, sú usporiadaní rovnako, ako boli na začiatku). Táto dátová štruktúra je o logaritmus pomalšia než spájaný zoznam, časovú zložitosť nám však nepokazí, lebo iné časti algoritmu sú pomalšie.
Ďalšiu dátovú štruktúru si musíme zvoliť na efektívne zistenie, ktorú udalosť máme spracovať ďalšiu – prechod na ďalšieho KSPáka, konkrétne predbehnutie, alebo odpovedanie na pristávacie miesto. Tieto udalosti chceme riešiť usporiadané podľa pozície, na ktorej sa udejú, a musíme do nej \(O(n+q)\) krát udalosť pridať, a teda aj \(O(n+q)\) krát vybrať a zmazať nasledujúcu udalosť. Toto vieme vykonať prioritnou frontou (napr. haldou), ako je priority_queue v C++. V tejto prioritnej fronte teda budeme mať aj náš zoznam predbehnutí. Z tohoto zoznamu sme však občas potrebovali aj mazať (keď nejaké predbehnutie prestalo byť aktuálne), čo bežná halda nepodporuje. To vyriešime nasledujúcou fintou: neaktuálne prvky nebudeme mazať, ale pri výbere z prioritnej fronty budeme kontrolovať, či je vyberaný prvok ešte aktuálny. Druhá možnosť je použiť ako prioritnú frontu usporiadanú množinu.
Budeme teda \(O(n+q)\) krát pridávať/mazať prvok z prioritnej fronty ktorá bude mať \(O(n+q)\) prvkov, toto nám zaberie \(O((n+q) \log (n+q))\) času a \(O(n+q)\) pamäte. Taktiež budeme musieť \(O(n)\) krát pridávať a vyhadzovať KSPákov zo spájaného zoznamu s poradím, čo nám zaberie \(O(n)\) času (alebo, ak použijeme usporiadanú množinu, \(O(n \log n)\) času) a \(O(n)\) pamäte. Dokopy teda celé naše riešenie zaberie \(O((n+q) \log (n+q))\) času a \(O( n+q)\) pamäte.
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct bezec
{
int x,id;
double v;
};
struct otazka
{
int y,id;
vector<int> odpoved;
};
struct udalost
{
double kde;
int typ; // 1 = novy KSPak, 2 = predbehnutie, 3 = pristatie
int id,id2; // id = id, id2 je id predbehnuteho KSPaka v pripade typ = 2
};
struct najskor
{
bool operator()(const udalost&a,const udalost&b) const
{
if(a.kde != b.kde)
return a.kde > b.kde; // najlavejsie udalosti najprv
return a.typ < b.typ;
}
};
struct zostupne
{
bool operator()(const bezec a,const bezec b) const
{
return a.x > b.x;
}
};
void vyries(vector<bezec> &KSPaci,vector<otazka> &pristatia)
{
priority_queue<udalost,vector<udalost>,najskor> udalosti;
set<bezec,zostupne> nepredbehnuti;
//predbehnutych KSPakov vyskrtneme, a uz ich budeme ignorovat
vector<bool> zaujimavi(KSPaci.size(),true);
int posledne_pristatie = -1; //
for(auto KSPak:KSPaci)
udalosti.push({KSPak.x,1,KSPak.id,-1});
for(auto pristatie:pristatia)
udalosti.push({pristatie.y,3,pristatie.id,-1});
while(!udalosti.empty())
{
udalost event = udalosti.top();
udalosti.pop();
int id = event.id;
if(event.typ == 1) // novy KSPak
{
// z KSPakov startujucich na rovnakej pozicii chceme len rychlejsieho
if(!nepredbehnuti.empty() && nepredbehnuti.begin()->x == KSPaci[id].x)
{
int id2 = nepredbehnuti.begin()->id;
if(KSPaci[id2].v > KSPaci[id].v)
{
zaujimavi[id] = false;
continue;
}
else
{
nepredbehnuti.erase(KSPaci[id2]);
zaujimavi[id2] = false;
}
}
// ak existuje nepredbehnuty KSPak, je rychlejsi, tak si zapiseme kedy nas predbehne
if(!nepredbehnuti.empty() && nepredbehnuti.begin()->v > KSPaci[id].v)
{
int id2 = nepredbehnuti.begin()->id;
double predbehne = KSPaci[id].x + (KSPaci[id].x - KSPaci[id2].x) / (KSPaci[id2].v - KSPaci[id].v) * KSPaci[id].v;
udalosti.push({predbehne,2,id2,id});
}
nepredbehnuti.insert(KSPaci[id]);
}
else if (event.typ == 2) // predbehnutie
{
int id2 = event.id2;
if(zaujimavi[id] == false)
continue; //pozostatok KSPaka, ktoreho uz niekto iny predbehol
if(zaujimavi[id2] == false)
continue; //toto sa moze stat v pripade, ze sme mali predbehnut KSPaka
// ktoreho hned na to 'predbehol' rychlejsi KSPak na rovnakej suradnici
// v tom pripade uz mame zapisane aj predbehnutie s tym rychlejsim, a budeme riesit to
if(posledne_pristatie != -1)
{
// skusime zapisat do odpovede aj tychto KSPakov, ak maju rovnaky cas ako ten najlepsi
double najlepsi = (pristatia[posledne_pristatie].y - (*nepredbehnuti.begin()).x ) / (*nepredbehnuti.begin()).v;
double my = (pristatia[posledne_pristatie].y - KSPaci[id].x) / KSPaci[id].v;
if(my == najlepsi)
{
pristatia[posledne_pristatie].odpoved.push_back(id);
pristatia[posledne_pristatie].odpoved.push_back(id2);
}
}
// zahodime predbehnuteho KSPaka
zaujimavi[id2] = false;
nepredbehnuti.erase(KSPaci[id2]);
auto it = nepredbehnuti.find(KSPaci[id]);
// tento KSPak je na cele, nema koho predbehnut
if(it == nepredbehnuti.begin()) continue;
it--;
id2 = it->id;
if(KSPaci[id2].v < KSPaci[id].v)
{
double predbehne = KSPaci[id2].x + (KSPaci[id2].x - KSPaci[id].x) / (KSPaci[id].v - KSPaci[id2].v) * KSPaci[id2].v;
udalosti.push({predbehne,2,id,id2});
}
}
else
{
posledne_pristatie = id;
if(!nepredbehnuti.empty())
{
pristatia[id].odpoved.push_back(nepredbehnuti.begin()->id);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,q;
cin >> n >> q;
if(n <= 3000 && q <= 3000)
{
//riesenie hrubou silou
return 0;
}
vector<bezec> KSPaci(n);
vector<otazka> pristatia(q);
for(int i=0;i<n;++i)
{
KSPaci[i].id = i;
cin >> KSPaci[i].x >> KSPaci[i].v;
}
for(int i=0;i<q;++i)
{
pristatia[i].id = i;
cin >> pristatia[i].y;
}
vyries(KSPaci,pristatia);
for(auto &pristatie:pristatia)
{
sort(pristatie.odpoved.begin(),pristatie.odpoved.end());
auto it = unique(pristatie.odpoved.begin(),pristatie.odpoved.end());
pristatie.odpoved.resize(distance(pristatie.odpoved.begin(),it));
cout << pristatie.odpoved.size();
for(auto KSPak:pristatie.odpoved)
cout << " " << KSPak+1;
cout << "\n";
}
return 0;
}A už len čelom vzad
No a čo nám od tohto riešenia chýba k verzii, keď sú KSPáci hala-bala rozmiestnení medzi pristátiami? Naše riešenie si vlastne vie poradiť s ľubovoľným vstupom, ak by naša otázka bola “pre každé pristávacie miesto povedz tých KSPákov, ktorí by sa k nemu dostali najrýchlejšie, keby všetci bežali doprava”. Stačí nám teda úlohu vyriešiť ešte raz, ale v opačnom smere – teraz všetci KSPáci budú bežať len doľava, a KSPákov, pristátia a predbehnutia budeme spracovávať v poradí sprava doľava. Ešte poznamenáme, že o dosť príjemnejšie na implementáciu ako skopírovanie celého kódu a menenie dátových štruktúr, aby teraz zoraďovali udalosti naopak ako predtým, je napísať si jednosmerné riešenie ako funkciu, spustiť ju raz na danom vstupe a následne celý vstup otočiť (všetkým KSPákom zmeníme súradnice z \(x_i\) na \(10^9-x_i\) a pristávacím miestam z \(y_i\) na \(10^9-y_i\)). Potom našu funkciu zavoláme ešte raz, a máme vyhraté. Treba len mierne pozmeniť zapisovanie odpovede – keď ideme KSPáka zapísať, najprv sa pozrieme, či už pre dané pristávacie miesto nemáme už nejakú odpoveď, a ak áno, aký čas majú KSPáci, ktorí tam boli predtým zapísaní.
Časová aj pamäťová zložitosť ostáva rovnaká – naše riešenie len použijeme dva krát.
#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
using namespace std;
struct bezec
{
int x,id;
double v;
};
struct otazka
{
int y,id;
vector<int> odpoved;
double cas = 100000001;
};
struct udalost
{
double kde;
int typ; // 1 = novy KSPak, 2 = predbehnutie, 3 = pristatie
int id,id2; // id = id, id2 je id predbehnuteho KSPaka v pripade typ = 2
};
struct najskor
{
bool operator()(const udalost&a,const udalost&b) const
{
if(a.kde != b.kde)
return a.kde > b.kde; // najlavejsie udalosti najprv
return a.typ < b.typ;
}
};
struct zostupne
{
bool operator()(const bezec a,const bezec b) const
{
return a.x > b.x;
}
};
void skus_odpovedat(bezec &KSPak,otazka &pristatie)
{
double cas = abs(pristatie.y - KSPak.x) / KSPak.v;
if(pristatie.cas > cas)
{
pristatie.odpoved = {KSPak.id};
pristatie.cas = cas;
}
else if (pristatie.cas == cas)
pristatie.odpoved.push_back(KSPak.id);
}
void vyries(vector<bezec> &KSPaci,vector<otazka> &pristatia)
{
priority_queue<udalost,vector<udalost>,najskor> udalosti;
set<bezec,zostupne> nepredbehnuti;
//predbehnutych KSPakov vyskrtneme, a uz ich budeme ignorovat
vector<bool> zaujimavi(KSPaci.size(),true);
int posledne_pristatie = -1; //
for(auto KSPak:KSPaci)
udalosti.push({KSPak.x,1,KSPak.id,-1});
for(auto pristatie:pristatia)
udalosti.push({pristatie.y,3,pristatie.id,-1});
while(!udalosti.empty())
{
udalost event = udalosti.top();
udalosti.pop();
int id = event.id;
if(event.typ == 1) // novy KSPak
{
// z KSPakov startujucich na rovnakej pozicii chceme len rychlejsieho
if(!nepredbehnuti.empty() && nepredbehnuti.begin()->x == KSPaci[id].x)
{
int id2 = nepredbehnuti.begin()->id;
if(KSPaci[id2].v > KSPaci[id].v)
{
zaujimavi[id] = false;
continue;
}
else
{
nepredbehnuti.erase(KSPaci[id2]);
zaujimavi[id2] = false;
}
}
// ak existuje nepredbehnuty KSPak, je rychlejsi, tak si zapiseme kedy nas predbehne
if(!nepredbehnuti.empty() && nepredbehnuti.begin()->v > KSPaci[id].v)
{
int id2 = nepredbehnuti.begin()->id;
double predbehne = KSPaci[id].x + (KSPaci[id].x - KSPaci[id2].x) / (KSPaci[id2].v - KSPaci[id].v) * KSPaci[id].v;
udalosti.push({predbehne,2,id2,id});
}
nepredbehnuti.insert(KSPaci[id]);
}
else if (event.typ == 2) // predbehnutie
{
int id2 = event.id2;
if(zaujimavi[id] == false)
continue; //pozostatok KSPaka, ktoreho uz niekto iny predbehol
if(zaujimavi[id2] == false)
continue; //toto sa moze stat v pripade, ze sme mali predbehnut KSPaka
// ktoreho hned na to 'predbehol' rychlejsi KSPak na rovnakej suradnici
// v tom pripade uz mame zapisane aj predbehnutie s tym rychlejsim, a budeme riesit to
if(posledne_pristatie != -1)
{
// skusime zapisat do odpovede aj tychto KSPakov, ak maju rovnaky cas ako ten najlepsi
skus_odpovedat(KSPaci[id],pristatia[posledne_pristatie]);
skus_odpovedat(KSPaci[id2],pristatia[posledne_pristatie]);
}
// zahodime predbehnuteho KSPaka
zaujimavi[id2] = false;
nepredbehnuti.erase(KSPaci[id2]);
auto it = nepredbehnuti.find(KSPaci[id]);
// tento KSPak je na cele, nema koho predbehnut
if(it == nepredbehnuti.begin()) continue;
it--;
id2 = it->id;
if(KSPaci[id2].v < KSPaci[id].v)
{
double predbehne = KSPaci[id2].x + (KSPaci[id2].x - KSPaci[id].x) / (KSPaci[id].v - KSPaci[id2].v) * KSPaci[id2].v;
udalosti.push({predbehne,2,id,id2});
}
}
else
{
posledne_pristatie = id;
if(!nepredbehnuti.empty())
{
skus_odpovedat(KSPaci[nepredbehnuti.begin()->id],pristatia[id]);
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,q;
cin >> n >> q;
vector<bezec> KSPaci(n);
vector<otazka> pristatia(q);
for(int i=0;i<n;++i)
{
KSPaci[i].id = i;
cin >> KSPaci[i].x >> KSPaci[i].v;
}
for(int i=0;i<q;++i)
{
pristatia[i].id = i;
cin >> pristatia[i].y;
}
// vyriesime pripad, ked KSPaci bezia doprava
vyries(KSPaci,pristatia);
// otocime vstup
for(auto &KSPak:KSPaci)
KSPak.x = 1000000000 - KSPak.x;
for(auto &pristatie:pristatia)
pristatie.y = 1000000000 - pristatie.y;
// vyriesime pripad, ked KSPaci bezia dolava
vyries(KSPaci,pristatia);
for(auto &pristatie:pristatia)
{
sort(pristatie.odpoved.begin(),pristatie.odpoved.end());
auto it = unique(pristatie.odpoved.begin(),pristatie.odpoved.end());
pristatie.odpoved.resize(distance(pristatie.odpoved.begin(),it));
cout << pristatie.odpoved.size();
for(auto KSPak:pristatie.odpoved)
cout << " " << KSPak+1;
cout << "\n";
}
return 0;
}z KSPákov začínajúcich na rovnakej pozícii môžeme všetkých, až na najrýchlejšieho, ignorovať↩
Diskusia
Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.
Pre pridávanie komentárov sa musíš prihlásiť.