Submission #830358

#	Time	Username	Problem	Language	Result	Execution time	Memory
830358		skittles1412	Teams (IOI15_teams)	C++17	0 / 100	4057 ms	15092 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] {};
        for (auto& a : q_arr) {
            q_cnt[a]++;
        }

        for (int pos = 1; pos <= n; pos++) {
            int evts[n + 1][2] {};
            for (auto& [ql, qr] : arr) {
                evts[ql][qr >= pos]++;
            }

            int lt = 0, gt = 0;
            for (int t = 1; t < pos; t++) {
                lt += evts[t][0];
                gt += evts[t][1];

                int cx = q_cnt[t] * t, sub = min(lt, cx);
                lt -= sub;
                cx -= sub;
                gt -= cx;

                if (gt < 0) {
                    dbg(pos, lt, gt);
                    return false;
                }
            }

            assert(!evts[pos][0]);
            gt += evts[pos][1];

            if (q_cnt[pos] * pos > gt) {
                dbg(pos, gt);
                return false;
            }
        }

        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