- محدودیت زمان: ۱۰ ثانیه (برای تمامی زبانهای برنامهنویسی)
- محدودیت حافظه: ۵۱۲ مگابایت (برای تمامی زبانهای برنامهنویسی)
در این مسئله، N گربه (با شمارههای 1 تا N) و M موش (با شمارههای 1 تا M) روی یک خط هستند. هر گربه و هر موش میخواهد از نقطهای به سمت نقطهای دیگر (شاید همان نقطه) روی این خط حرکت کند. طبیعتاً، گربهها هم میخواهند موشها را بخورند. هر گربه و هر موش با سرعت ثابت 1 حرکت میکند.
برای هر i معتبر، i-امین گربه در ابتدا در نقطهی ai خواب است. در زمان si، این گربه بیدار میشود و به سمت نقطهی نهایی bi با سرعت ثابت و بدون هیچ پرشی حرکت میکند (بنابراین در زمان ei=si+∣ai−bi∣ به این نقطه میرسد). پس از رسیدن به نقطهی bi، دوباره به خواب میرود.
برای هر i معتبر، i-امین موش در ابتدا در نقطهی ci پنهان شده است. در زمان ri، این موش از پنهانی در میآید و به سمت نقطهی نهایی di به همان صورتی که گربهها حرکت میکنند - با سرعت ثابت و بدون هیچ پرشی - حرکت میکند و در زمان qi=ri+∣ci−di∣ (اگر خورده نشود) به این نقطه میرسد. پس از رسیدن به نقطهی di، دوباره پنهان میشود.
اگر یک گربه و یک موش یکدیگر را ببینند (یعنی در یک نقطه و در یک زمان قرار بگیرند)، گربه موش را میخورد و موش ناپدید میشود و نمیتواند توسط گربهای دیگر خورده شود. یک گربهی خوابیده نمیتواند موشی را بخورد و یک موش پنهان نمیتواند خورده شود - به صورت دقیقتر، گربهی i تنها در صورتی میتواند موش j را بخورد که در زمان t با هم برخورد کنند به طوری که si≤t≤ei و rj≤t≤qj برقرار باشد.
وظیفهی شما این است که پیدا کنید کدام موشها توسط کدام گربهها خورده میشوند. تضمین میشود که دو گربه به طور همزمان با یک موش برخورد نمیکنند.
ورودی🔗
- خط اول ورودی شامل یک عدد صحیح T است که تعداد سناریوها را نشان میدهد. توضیحات مربوط به T سناریو در ادامه آمده است.
- خط اول هر سناریو شامل دو عدد صحیح N و M است که با یک فاصله از هم جدا شدهاند (در ابتدا N میآید و سپس M).
- N خط در ادامه آمده است. برای هر i (1≤i≤N)، خط i-ام از این خطوط شامل سه عدد صحیح ai، bi و si است که با یک فاصله از هم جدا شدهاند.
- M خط دیگر در ادامه آمده است. برای هر i (1≤i≤M)، خط i-ام از این خطوط شامل سه عدد صحیح ci، di و ri است که با یک فاصله از هم جدا شدهاند.
خروجی🔗
برای هر سناریو، M خط چاپ کنید. برای هر i معتبر، خط i-ام از این خطوط باید شامل یک عدد صحیح باشد: شماره گربهای که موش i-ام را میخورد و یا −1 اگر هیچ گربهای این موش را نخورده است.
محدودیتها🔗
- 1≤T≤10
- 0≤N≤1,000
- 1≤M≤1,000
- 1≤ai,bi,si≤109 برای هر i معتبر
- 1≤ci,di,ri≤109 برای هر i معتبر
- همه موقعیتهای اولیه و نهایی همهی گربهها و موشها متمایز هستند. البته درمورد هر موش خاص موقعیت شروع و پایان آن میتواند یکسان باشد. و درمورد هر گربهی خاص موقعیت شروع و پایان آن میتواند یکسان باشد.
مثال🔗
ورودی نمونه ۱🔗
خروجی نمونه ۱🔗