Задача 82: Проходной балл

Условие задачи:

Одна Очень Престижная Олимпиада, как и все престижные олимпиады в последнее время, состоит из двух туров - регионального и заключительного. Правила отбора во второй тур (заключительный этап) просты:

Призеры олимпиады прошлого года приглашаются на заключительный этап вне зависимости от набранных ими в первом туре баллов.
Все участники, набравшие не меньше баллов, чем установленный жюри проходной балл, проходят во второй тур.
Если в каком-либо из регионов ни один участник по первым двум правилам во второй тур не прошел, то на заключительный этап приглашается участник из этого региона, набравший в нем максимальное количество баллов (это не касается регионов, от которых участников не было).
На второй тур можно пригласить не более \(M\) участников.
Известно, что никакие два участника не набрали одинаковое количество баллов. По информации о результатах первого тура помогите жюри установить минимально возможный проходной балл, при котором все правила отбора будут выполнены.

Входные данные:

В первой строке входного файла содержатся три целых числа \(N\), \(M\) и \(R\) - число участников первого тура, максимально возможное число участников второго тура и число регионов, из которых могли быть участники \((1 <= M <= N)\). Далее в \(N\) строках содержатся результаты каждого из участников. Каждая строка состоит из четырех целых чисел. Сначала идет \(id\) - уникальный идентификатор участника \((1 <= id <= N)\), далее номер региона \(region\), в котором данный участник учится \((1<=region<=R)\), затем \(score\) - число баллов, набранных участником, четвертое число равно 1, если участник является призером олимпиады прошлого года, и 0 - в противном случае.

Гарантируется, что все идентификаторы участников различны, никакие два участника не набрали одинаковое число баллов, и выполнить все правила отбора возможно.

Выходные данные:

Выведите одно число - минимальный проходной балл, который можно установить.

Решение:

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <algorithm>

using namespace std;

int n, ma, r_z, priz;
vector <tuple <int, int, int, int>> u;
set <int> okrug_priz;
set <int> okrug;

bool comp_sort_u(tuple<int, int, int, int> a, tuple<int, int, int, int> b) {
    return get<2>(a) > get<2>(b);
}

bool check(int ans, set <int> ok) {
    int s = priz;
    for (auto t : u) {
        if (s > ma) {
            return false;
        }
        if (get<2>(t) >= ans) {
            s += 1;
            ok.insert(get<1>(t));
        }
        else {
            break;
        }
    }
    return s + okrug.size() - ok.size() <= ma;
}


int main()
{
    cin >> n >> ma >> r_z;
    long long l = 1000000001;
    long long r = -1;
    priz = 0;

    int i_id, i_region, i_score, i_prev;
    for (int i = 0; i < n; i++) {
        cin >> i_id >> i_region >> i_score >> i_prev;
        okrug.insert(i_region);
        if (i_prev == 1) {
            priz += 1;
            okrug_priz.insert(i_region);
            continue;
        }
        if (i_score < l) {
            l = i_score;
        }
        if (i_score > r) {
            r = i_score;
        }
        u.push_back(make_tuple(i_id, i_region, i_score, i_prev));
    }
    sort(u.begin(), u.end(), comp_sort_u);
    l -= 1;
    r += 1;

    int m;
    while (r - l > 1) {
        m = (l + r) / 2;
        if (check(m, okrug_priz)) {
            r = m;
        }
        else {
            l = m;
        }
    }
    cout << r << endl;
    return 0;
}

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик