Submission #830281

#	Time	Username	Problem	Language	Result	Execution time	Memory
830281		skittles1412	Teams (IOI15_teams)	C++17	0 / 100	4077 ms	14736 KiB

teams

#include "bits/extc++.h"

using namespace std;

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t;
    ((cerr << " | " << u), ...);
    cerr << endl;
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__)
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int(std::size(x))

template <typename Cb>
struct Cmp {
    Cb cb;

    Cmp(Cb cb) : cb(cb) {}

    template <typename T>
    bool operator()(const T& a, const T& b) const {
        return cb(a) < cb(b);
    }
};

struct Solver {
    vector<pair<int, int>> arr;

    Solver() {}
    Solver(const vector<pair<int, int>>& _arr) : arr(_arr) {
        sort(begin(arr), end(arr),
             Cmp([&](const pair<int, int>& p) -> int { return p.second; }));
    }

    bool query(vector<int> q_arr) {
        sort(begin(q_arr), end(q_arr));

        int n = sz(arr);

        if (accumulate(begin(q_arr), end(q_arr), long(0)) > n) {
            return false;
        }

        int q_cnt[n + 1] {}, evt_pos[n + 2] {}, evt_neg[n + 2] {};
        for (auto& a : q_arr) {
            q_cnt[a]++;
        }
        for (auto& [ql, qr] : arr) {
            evt_pos[ql]++;
            evt_neg[qr + 1]--;
        }

        int open = 0, tot = 0;
        for (int t = 0; t <= n; t++) {
            tot += evt_neg[t];
            open = min(open, tot);
            tot += evt_pos[t];
            open += evt_pos[t];

            if (q_cnt[t] * t > open) {
                dbg(t, q_cnt[t], t, open, tot);
                return false;
            }
            open -= q_cnt[t] * t;
        }

        return true;
    }
} solver;

void init(int n, int arrl[], int arrr[]) {
    vector<pair<int, int>> arr;
    for (int i = 0; i < n; i++) {
        arr.emplace_back(arrl[i], arrr[i]);
    }

    solver = Solver(arr);
}

int can(int m, int arr[]) {
    return solver.query(vector<int>(arr, arr + m));
}

Compilation message (stderr)

teams.cpp: In constructor 'Cmp<Cb>::Cmp(Cb)':
teams.cpp:31:12: warning: declaration of 'cb' shadows a member of 'Cmp<Cb>' [-Wshadow]
   31 |     Cmp(Cb cb) : cb(cb) {}
      |         ~~~^~
teams.cpp:29:8: note: shadowed declaration is here
   29 |     Cb cb;
      |        ^~
teams.cpp: In instantiation of 'Cmp<Cb>::Cmp(Cb) [with Cb = Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const std::pair<int, int>&)>]':
teams.cpp:45:74:   required from here
teams.cpp:31:12: warning: declaration of 'cb' shadows a member of 'Cmp<Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const std::pair<int, int>&)> >' [-Wshadow]
   31 |     Cmp(Cb cb) : cb(cb) {}
      |         ~~~^~
teams.cpp:29:8: note: shadowed declaration is here
   29 |     Cb cb;
      |        ^~
teams.cpp:31:12: warning: declaration of 'cb' shadows a member of 'Cmp<Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const std::pair<int, int>&)> >' [-Wshadow]
   31 |     Cmp(Cb cb) : cb(cb) {}
      |         ~~~^~
teams.cpp:29:8: note: shadowed declaration is here
   29 |     Cb cb;
      |        ^~
teams.cpp:31:12: warning: declaration of 'cb' shadows a member of 'Cmp<Solver::Solver(const std::vector<std::pair<int, int> >&)::<lambda(const std::pair<int, int>&)> >' [-Wshadow]
   31 |     Cmp(Cb cb) : cb(cb) {}
      |         ~~~^~
teams.cpp:29:8: note: shadowed declaration is here
   29 |     Cb cb;
      |        ^~

• Subtask 1: 0 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23