제출 #592613

#제출 시각아이디문제언어결과실행 시간메모리
592613hltk커다란 상품 (IOI17_prize)C++17
0 / 100
8 ms3536 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; vector<pii> C; pii m_ask(int i) { if (C[i].first != -1) return C[i]; auto a = ask(i); return C[i] = {a[0], a[1]}; } // 1, 2, 5, 26, 677 int find_best(int n) { C.assign(n, {-1, -1}); if (n <= 7000) { for (int i = 0; i < n; ++i) { auto [a, b] = m_ask(i); if (a + b == 0) { return i; } } throw; } int B = n / 500; vector<int> pt; for (int i = 0; i < n; i += B) { pt.push_back(i); } int t = 0; for (int i : pt) { auto [a, b] = m_ask(i); t = max(t, a + b); } auto check = [&](int i) { auto [a, b] = m_ask(i); return a + b != t; }; int jt = 0; for (int i = 0; i < n; ++i) { if (check(i)) { auto [a, b] = m_ask(i); if (a + b == 0) return i; } else { auto same = [&](int j) { return !check(j) && m_ask(j).second == m_ask(i).second; }; int st = i, ed = n - 1; while (pt[jt] <= i) ++jt; for (int it = jt; it < (int) pt.size(); ++it) { int j = pt[it]; if (same(j)) { st = j; } else { ed = j - 1; break; } } while (st < ed) { int m = (st + ed) / 2; if (!same(m)) ed = m; else st = m + 1; } i = st - 1; assert(check(st)); } } }

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:32:14: warning: control reaches end of non-void function [-Wreturn-type]
   32 |  vector<int> pt;
      |              ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...