سسمی باز شو (Sesame)

سندباد پس از شرکت در آزمون المپیاد کامپیوتر، تصمیم گرفت تا بجای حل سوالات رمز اکانت ادمین را پیدا کرده تا به راه‌حل‌ها دسترسی پیدا کند.

سندباد در روز‌های اخیر پشت در سایت حرف مسئولین آزمون را شنود کرده و متوجه شده که با دستور سسمی باز شو و وارد کردن رمز ادمین می‌تواند به راه‌حل سوالات دسترسی پیدا کند. همچنین در طی این شنود‌ها او متوجه شد که رمز اکانت ادمین جایگشت $p_1, p_2, \ldots, p_n$ از اعداد $1$ تا $n$ است.

سندباد در طی آزمون پس از احضار کردن غول چراغ جادو می‌تواند از او ۲ نوع سوال در مورد رمز ادمین بپرسد:

1. با پرسیدن این نوع سوال و دادن یک اندیس $i$ ($ 1 \leq i \leq n$) به غول چراغ جادو، سندباد می‌تواند عضو $p_i$ رمز ادمین را پیدا کند.

2. با پرسیدن این نوع سوال و ورودی دادن دو اندیس $l$ و $r$ به غول چراغ جادو به طوری که $1 \leq l \leq r < n$، غول چراغ جادو مقدار $$\min(\max\{p_l, p_{l + 1}, p_{l + 2}, \ldots , p_{r}\}, \max\{p_{r + 1}, p_{r + 2}, p_{r + 3}, \ldots , p_{n}\})$$ را به سندباد می‌گوید. به عبارت دیگر پس از انجام این پرسش، غول چراغ جادو مقدار بیشینه دو بازه $[l, r]$ و $[r + 1, n]$ را حساب کرده و بین این دو مقدار، مقدار کمینه را به سندباد اطلاع می‌دهد.

غول چراغ جادو که نمی‌خواهد زیاد بی‌اخلاقی کند و مستقیما رمز را به سندباد بگوید، تصمیم گرفته تا تنها به حداکثر ۱ سوال از سوالات نوع اول سندباد پاسخ دهد. از طرف دیگر هر چقدر سندباد زمان بیشتری را صرف پرسیدن سوالات از غول چراغ جادو بکند، مسئولین آزمون به تقلب او بیشتر مشکوک می‌شوند، برای همین سندباد سعی دارد تا جای ممکن با سوالات کمتری رمز اکانت ادمین را بفهمد. سندباد چیزی از المپیاد کامپیوتر نمی‌داند برای همین شما باید به او کمک کنید تا به رمز اکانت ادمین دست پیدا کند.

در این سوال شما اجازه خواندن از ورودی یا نوشتن در خروجی را ندارید. تنها راه تبادل اطلاعات با استفاده از توابعی که در ادامه معرفی می‌کنیم خواهد بود.

در صورت هرگونه تلاش برای خواندن از ورودی یا نوشتن در خروجی یا استفاده از تابع exit نمره شما صفر می‌شود.

std::vector<int> open_sesame(int n)

شما باید این تابع را پیاده کنید. در هر تست این تابع یک بار فراخوانی می‌شود که در آن اندازه جایگشت به شما داده شده است. در این تابع به کمک فراخوانی توابع ask_cell و ask_range به محتوای جایگشت دست پیدا کنید. اعضای جایگشت را به صورت بردار (vector) $p_1, p_2, \ldots, p_n$ برگردانید.

در صورتی که تعداد اعضای بردار خروجی برابر با $n$ نباشد خطای protocol violation را دریافت خواهید کرد.

int ask_cell(int i)

با استفاده از این تابع که در اختیار شما قرار گرفته است می‌توانید سوالی از نوع اول بپرسید. خروجی تابع برابر عضو $p_i$ جایگشت خواهد بود. در هر تست فقط یک بار می‌توانید این تابع را صدا بزنید.

در صورتی که اندیس داده شده در شرط $1 \leq i \leq n$ صدق نکند یا این تابع بیش از یک بار صدا زده شود، خطای protocol violation را دریافت خواهید کرد.

int ask_range(int l, int r)

با فراخوانی این تابع می‌توانید سوالاتی از نوع دوم بپرسید. خروجی تابع برابر $$\min(\max\{p_l, p_{l + 1}, p_{l + 2}, \ldots , p_{r}\}, \max\{p_{r + 1}, p_{r + 2}, p_{r + 3}, \ldots , p_{n}\})$$ خواهد بود. محدودیتی برای تعداد سوال از این نوع وجود ندارد.

دقت کنید که $1 \leq l \leq r < n$ باید برقرار باشد. در غیر این صورت خطای protocol violation را دریافت خواهید کرد.

فایل‌های مربوط به سوال را دانلود کنید. راه حل خود را درون sesame.cpp پیاده‌سازی کنید. برای کامپایل و اجرا کردن برنامه باید compile_cpp.sh را اجرا کنید. سپس فایل اجرایی sesame را که توسط compile_cpp.sh تولید شده است اجرا کنید.

فرمت ورودی ارزیاب نمونه:

n
p[1] p[2] ... p[n]

فرمت خروجی: در صورتی که اجرا موفقیت‌آمیز باشد، در خط اول تعداد سوال‌های پرسیده شده (شامل نوع اول و دوم) نوشته می‌شود. در خط دوم جایگشتی که تابع open_sesame برگردانده است چاپ می‌شود.

• زیرمسئله اول (۳ نمره): $2 \leq n \leq 3$
• زیرمسئله دوم (۵ نمره): $n \leq 8$
• زیرمسئله سوم (۱۱ نمره): جایگشت به صورت تصادفی با توزیع یکنواخت از میان $n!$ جایگشت انتخاب شده است.
• زیرمسئله چهارم (۱۱ نمره): $p_i < n$ برای $ 1 \leq i \leq \lceil n / 2 \rceil$
• زیرمسئله پنجم (۷۰ نمره): بدون محدودیت اضافی

فرض کنید بیشینه پرسش‌های انجام شده در یک تست از یک زیرمسئله (شامل نوع اول و دوم) برابر $T$ باشد. در صورتی که نمره زیرمسئله برابر $P$ باشد نمره شما از این زیرمسئله به کمک تابع $f(T,P)$ محاسبه می‌شود:

• $T \leq 400\,000$ : $f(T, P) = P$
• $T \leq 450\,000$ : $f(T, P) = 0.7 \times P$
• $T \leq 600\,000$ : $f(T, P) = 0.2 \times P$
• $T > 600\,000$ : $f(T, P) = 0$

• $2 \leq n \leq 300\,000$

خط اول خروجی برابر تعداد پرسش‌هاست. در خط دوم جایگشتی که بدست آمده چاپ شده است. در جدول زیر توابع پرسیده شده در نمونه ورودی اول و مقدار خروجی این توابع نشان داده شده است.

با پرسش اول متوجه می‌شویم ۱ می‌تواند فقط در جایگاه اول باشد. با پرسش دوم نیز متوجه می‌شویم که فقط در جایگاه دوم می‌تواند عدد ۲ قرار گیرد. پرسش سوم فارغ از حالات ممکن همواره ۳ می‌شود. با پرسش چهارم مقدار عضو چهارم را متوجه می‌شویم و مقدار عضو سوم جایگشت نیز یکتا مشخص می‌شود.