Решение задачи Сборка контеста с Codeforces

С пояснением   Просмотров: 28


Аркадий координирует раунды на некой малоизвестной платформе по спортивному программированию. В каждом раунде дается n задач различной сложности, сложности задач пронумерованы от 1 до n.

Для того, чтобы провести раунд, Аркадию нужны n новых (ранее не использованных) задач, по одной задаче каждой сложности. Пока что Аркадий придумывает все задачи сам, но, к сожалению, он не может придумать задачу конкретной сложности. Вместо этого он всегда придумывает некоторую новую задачу, оценивает ее сложность от 1 до n и записывает в банк задач.

Каждый раз, когда Аркадий может выбрать из банка задач n новых задач различной сложности, он проводит раунд из этих задач и вычеркивает их из банка. Аркадий не придумывает несколько задач одновременно, поэтому, если он может провести раунд после того, как придумал очередную задачу, он сразу это делает.

Вам дана последовательность сложностей задач, которые придумывал Аркадий. Для каждой придуманной задачи определите, провел ли Аркадий раунд после придумывания этой задачи. Изначально банк задач был пуст.

Код

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<21;
int niz[maxn], cnt[maxn];
int main()
{
	int n, m, a;
	cin >> n >> m;
	for(int i=0;i<m;i++)
	{
		cin >> a;
		cnt[a]++;
		niz[cnt[a]]++;
		cout << (niz[cnt[a]] == n);
	}
	return 0;
}

         

Администратор Photo Автор: Администратор


Будем поддерживать массив, сколько задач придумано каждой конкретной сложности i — cnti и сколько задач уже придумано на контест j — existj. Тогда если мы в качестве очередной задачи придумали задачу со сложностью c, пересчитаем cntc=cntc+1, existcntc=existcntc+1. Пусть мы уже дали k контестов. Тогда после добавления очередной задачи нам лишь необходимо проверить, что existk=n, в таком случае мы можем дать очередной контест, иначе нет.

Сложность — O(m).


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться