Submission #830358

#TimeUsernameProblemLanguageResultExecution timeMemory
830358skittles1412Teams (IOI15_teams)C++17
0 / 100
4057 ms15092 KiB
#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;
      |        ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...