제출 #295461

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295461		Haunted_Cpp	커다란 상품 (IOI17_prize)	C++17	95.54 / 100	74 ms	15224 KiB

prize

    #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) {
      if (n == 1) {
        return 0;
      }
      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 < 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;
        }
      }
      const int start_location = best_way.second;
      auto solve = [&](int lo, int hi) {
        int idx = lo;
        while(idx < hi) {
          pair<int, int> res = perguntar(idx);
          if (calc_score(res) == calc_score(perguntar(start_location))) {
            int l = max(idx, find(res));
            int r = min(hi, rightmost(l));
            while(l < r) {
              const int mid = l + (r - l) / 2 + 1;
              pair<int, int> cur = perguntar(mid);
              if (res == cur) {
                l = mid;
              } else {
                r = mid - 1;
              }
            }
            idx = l + 1;
          } else {
            if (calc_score(res) == 0) {
              return idx;
            }
            ++idx;
          }
        }
      };
      return solve(start_location, n - 1);
    }

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

prize.cpp: In lambda function:
prize.cpp:73:7: warning: control reaches end of non-void function [-Wreturn-type]
   73 |       };
      |       ^

• Subtask 1: 20 / 20
• Subtask 2: 75.54 / 80