제출 #548082

#제출 시각아이디문제언어결과실행 시간메모리
548082jhwest2커다란 상품 (IOI17_prize)C++17
20 / 100
80 ms2748 KiB
#include "prize.h" #include <bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma optimize using namespace std; const int M = 2e5 + 10; vector<int> r; pair<int, int> A[M]; tuple<int, int, int, int> Q[M << 2]; inline pair<int, int> doAsk(int i) { if (A[i].first != -1) { return A[i]; } r = ask(i); return A[i] = { r[0], r[1] }; } int find_best(int n) { for (int i = 0; i < n; i++) { A[i].first = -1; } vector<int> I(n), J; for (int i = 0; i < n; i++) { I[i] = i; } int c = 0; while (I.size() != 1) { if (++c > 5) { exit(-1); } int x = 0; for (int j = 0; j < min((int)I.size(), (int)sqrt(I.size()) + 20); j++) { auto [a, b] = doAsk(I[j]); x = max(x, a + b); } int p = 0; Q[p++] = { 0, 0, 0, (int)I.size() - 1 }; while (p != 0) { auto [l, r, lo, hi] = Q[--p]; if (lo == hi) { J.push_back(I[lo]); continue; } int m = lo + hi >> 1; auto [vl, vr] = doAsk(I[m]); int c = 0, off = 0, ll = m, rr = m; while (vl + vr != x) { J.push_back(I[m + off]); c += 1; if (off <= 0) { off = -off + 1; rr = m + off; } else { off = -off; ll = m + off; } if (m + off < lo || m + off > hi) { break; } auto [nl, nr] = doAsk(I[m + off]); vl = nl; vr = nr; } if (m + off < lo || m + off > hi) { continue; } if (off <= 0) { if (l + vr != x) Q[p++] = { l, vr, lo, m + off }; if (vl + c + r != x) Q[p++] = { vl + c, r, m - off + 1, hi }; } else { if (l + vr + c != x) Q[p++] = { l, vr + c, lo, m - off }; if (vl + r != x) Q[p++] = { vl, r, m + off, hi }; } } I = J; J.clear(); sort(I.begin(), I.end()); } return I[0]; }

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

prize.cpp:7: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    7 | #pragma optimize
      | 
prize.cpp: In function 'int find_best(int)':
prize.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |    int m = lo + hi >> 1;
      |            ~~~^~~~
prize.cpp:55:24: warning: variable 'll' set but not used [-Wunused-but-set-variable]
   55 |    int c = 0, off = 0, ll = m, rr = m;
      |                        ^~
prize.cpp:55:32: warning: variable 'rr' set but not used [-Wunused-but-set-variable]
   55 |    int c = 0, off = 0, ll = m, rr = m;
      |                                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...