Областная олимпиада по информатике, 2018 год, 10-11 класс

(Тима и Рама) На доске в ряд написано $N$ целых чисел. Темірлан и Рамазан играют в следующую игру:

• Они будут ходить по очереди, первым начинает Темірлан.
  
• На каждом ходу игрок может стереть с доски любое ненулевое количество чисел с начала, или с конца. Но нельзя стереть все числа.
  
• Игра закончится, когда на доске останется ровно одно число. Темірлан хочет минимизировать последнее число, а Рамазан хочет максимизировать это число.
  

Пока Темірлан отошел, Рамазан хочет стереть ровна $K$ чисел. Он может стереть любые числа. Когда Темірлан вернется, они начнут играть как обычно, но на доске будет написано $N-K$ чисел.
Для каждого из $Q$ чисел $K_1,K_2, ..., K_Q$, Рамазан хочет узнать, какое значение у последнего оставшегося числа, если он заранее сотрет $K_i$ чисел, и оба игрока играют оптимально?

Формат входных данных:

В первой строке находится одно целое число $N$.
Во второй строке находятся $N$ целых числа $A_1,A_2,...,A_N (1 \le A_i \le 10^6)$ --- числа написанные на доске.
В третьей строке находится одно целое число $Q$.
В четвертой строке находятся $Q$ целых числа $K_1,K_2,...,K_Q(0 \le K_i \le N - 1)$.

Формат выходных данных:

Выведите через пробел $Q$ чисел, $i$-е из них, значения последнего оставшегося числа, если Рамазан заранее сотрет $K_i$ чисел.

Примеры:

1.Вход:

4
1 4 2 3
4
0 1 2 3

Ответ:

1 3 3 4

2.Вход:

3
5 5 5
3
0 1 2

Ответ:

5 5 5

3.Вход:

6
2 7 5 4 8 10
3
3 5 2

Ответ:

7 10 7

Замечание:

В первом тесте при $K=3$, Рамазану выгодно стереть первое,второе и четвертое числа.

Система оценки:

Задача содержит 50 тестов, каждая из которых весят 2 балла.
Ограничения которые присутствуют в тестах:

• 3 теста: Первые три теста является тестами из примеров
  
• 5 тестов: $1 \le N \le 3, Q = 1, K_1 = 0$
  
• 10 тестов: $1 \le N \le 100, Q = 1, K_1 = 0$
  
• 12 тестов: $1 \le N \le 10^5, 1\le Q \le 2, 0 \le K_i \le 1$
  
• 10 тестов: $1 \le N \le 10^5, 1 \le Q \le 10^5,0 \le K_i \le N - 1$
  
• 10 тестов: $1 \le N \le 10^6, 1 \le Q \le 10^6, 0 \le K_i \le N - 1$
  

( Temirlan Satylkhanov )

Комментарий/решение

Когда именно выдается вердикт Check Failed?

показать/скрыть код

#include <bits/stdc++.h>
#define f first
#define se second
using namespace std;
const int N = (int)(1e6 + 123);
pair <int , int> a[N];
int k[N] , ans[N] , b[N];
set <int> st;
int main() {
    int n;
    cin >> n;
    for (int i=1; i<=n; i++) {
        cin >> a[i].f;
        b[i] = a[i].f;
        a[i].se = i;
    }
    sort(a + 1 , a + 1 + n);
    for (int i=1; i<=n; i++) st.insert(i);
    for (int i=0; i<n; i++) {
        ans[i] = min(b[*st.begin()] , b[*st.rbegin()]);
        st.erase(a[i+1].se);
    }
    int q;
    cin >> q;
    for (int i=1; i<=q; i++) cin >> k[i];
    for (int i=1; i<=q; i++) cout <<ans[k[i]]<<" ";
    return 0;
}

Работает на претестах но говорит "ошибка проверки" что это значит?

исправлена ошибка в проверяющей системе. попробуйте переотправить.

Заработала спасибо!

можно разбор

А как проверить решение? В этой задаче нельзя же проверить.

админ можно разбор этой задачи

Можно доказать, если есть последовательность $a_1, a_2, ..., a_n$ то в конце останется число $min(a_1,a_n)$

Для того что бы получить число С мы должны на префиксе жадно удалить все числа меньше С и на суффиксе тоже. Если удалили $len$ чисел то $ans[len] >= C$.

показать/скрыть код

const int N = int(1e6) + 10, mod = int(1e9)  + 7; 

int n,q, a[N];

int mx, pref[N], suf[N], ans[N];

int main () {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	mx = 0;
	for(int i = 1; i <= n; i++){
		for(int j = mx + 1; j <= a[i]; j++){
		    pref[j] = i;
		}
		mx = max(mx, a[i]);
	}
	mx = 0;
	for(int i = n; i > 0; i--){
		for(int j = mx + 1; j <= a[i]; j++){
			suf[j] = i;
		}
		mx = max(mx, a[i]);
	}

	for(int i = 1, len; i <= mx; i++){
		len = pref[i] - 1  + n - suf[i];
		ans[len] = i;
	}
	for(int i = 1; i <= n; i++){
		ans[i] = max(ans[i - 1], ans[i]);
	}
	scanf("%d", &q);
	for(int i = 1,k; i <= q; i++){
		scanf("%d", &k);
		printf("%d", ans[k]);
		if(i < q) printf(" ");
	}


return 0;
}

скажите пожалуйста 10 тест

Почему ваше решение не ловит TLE, если асимптотика O($n * max(a_i)$)

Асимптотика $O(n + max(a_i))$.

Главное построить массивы prefix и suffix "проходом слева направо"

10й тест огромный.