المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۷:سوال ۲

شرکت هیولاها

در شرکت هیولاها، $n$ هیولا مشغول به کار هستند. کمیته بازیابی اطلاعات قصد دارد هیولاها را بر حسب میزان حقوقی که می‌گیرند مرتب کند. مشکل نحوه‌ی صحبت هیولاها با آدم‌ها است. ما نمی‌توانیم مستقیما از هیولاها مقدار حقوقشان را بپرسیم. تنها سوالی که می‌توانیم بپرسیم این است: «آیا هیولای $i$ کم‌تر از هیولای $j$ حقوق می‌گیرد؟»

می‌دانیم هیچ دو هیولایی مقدار حقوق برابر ندارند. به کمیته بازیابی اطلاعات کمک کنید تا با تعداد کمی پرسش، هیولاها را بر حسب حقوق مرتب کند.

شما می‌توانید حداکثر $2\times 10^6$ سوال از هیولاها بپرسید وگرنه هیولاها عصبانی می‌شوند و همه چیز را نابود می‌کنند.

برنامه‌ای بنویسید که:

  • تعداد هیولاها ($n$) را از کتاب‌خانه پیوندی بخواند.
  • به کمک کتاب‌خانه‌ی پیوندی سوالات مورد نظر را از شرکت هیولاها بپرسد.
  • به کتاب‌خانه‌ی پیوندی گزارش دهد ترتیب هیولاها بر حسب حقوق چگونه است.

ورودی

خروجی

محدودیت‌ها

  • محدودیت زمان: ۵ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه

ابزار صفحه