제출 #295452

#제출 시각아이디문제언어결과실행 시간메모리
295452Haunted_Cpp커다란 상품 (IOI17_prize)C++17
90 / 100
140 ms15532 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 2e5 + 5; vector<vector<int>> dp(MAX_N); map<int, set<int> > memo[MAX_N]; set<int> query; int find_best(int n) { pair<int, int> best_way = {-1, -1}; auto perguntar = [&](int delta) -> pair<int, int> { if (dp[delta].empty()) { dp[delta] = ask(delta); } vector<int> res = dp[delta]; memo[dp[delta][0]][dp[delta][1]].insert(delta); query.insert(delta); return {res[0], res[1]}; }; auto calc_score = [&](const pair<int, int> &res) { return res.first + res.second; }; auto find = [&](const pair<int, int> &res) { const int l = res.first; const int r = res.second; if (memo[l][r].empty()) return -1; return *memo[l][r].rbegin(); }; auto rightmost = [&](int idx) -> int { ++idx; auto where = query.lower_bound(idx); if (where == query.end()) return 1e9; return *where; }; for (int i = 0; i < min(n, 500); i++) { const int idx = i; pair<int, int> res = perguntar(idx); best_way = max(best_way, {calc_score(res), idx}); if (calc_score(res) == 0) { return i; } } int start_location = best_way.second; while(start_location < n) { pair<int, int> cur = perguntar(start_location); int s = cur.first + cur.second; if (s == best_way.first) { //~ if (start_location + 10 >= n) { //~ ++start_location; //~ continue; //~ } //~ pair<int, int> few_nxt = perguntar(start_location + 10); //~ if (few_nxt != cur) { //~ ++start_location; //~ continue; //~ } int lo = start_location; int hi = n - 1; while(lo < hi) { const int mid = lo + (hi - lo) / 2 + 1; pair<int, int> nxt = perguntar(mid); if (nxt.first == 0 && nxt.second == 0) { return mid; } if (nxt != cur) { hi = mid - 1; } else { lo = mid; } } start_location = lo + 1; } else { if (s == 0) { return start_location; } ++start_location; } } return -1; }

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:25:8: warning: variable 'find' set but not used [-Wunused-but-set-variable]
   25 |   auto find = [&](const pair<int, int> &res) {
      |        ^~~~
prize.cpp:31:8: warning: variable 'rightmost' set but not used [-Wunused-but-set-variable]
   31 |   auto rightmost = [&](int idx) -> int {
      |        ^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...