제출 #565314

#제출 시각아이디문제언어결과실행 시간메모리
565314hoanghq2004커다란 상품 (IOI17_prize)C++14
90 / 100
84 ms6056 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include "prize.h" using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>; // //static const int max_q = 10000; //static int n; //static int query_count = 0; //static vector<int> g; //static vector<vector<int> > rank_count; // //vector<int> ask(int i) { // query_count++; // if(query_count > max_q) { // cerr << "Query limit exceeded" << endl; // exit(0); // } // // if(i < 0 || i >= n) { // cerr << "Bad index: " << i << endl; // exit(0); // } // // vector<int> res(2); // res[0] = rank_count[g[i] - 1][i + 1]; // res[1] = rank_count[g[i] - 1][n] - res[0]; // return res; //} int find_best(int n) { int tot = 0; srand(time(nullptr)); int m = min(n, 10); vector <int> used(n, 0); vector <vector <int>> ans(n); auto get = [&](int i) { if (ans[i].size()) return ans[i]; ans[i] = ask(i); return ans[i]; }; while (m--) { int i = rand() % n; while (used[i]) i = rand() % n; used[i] = 1; vector <int> cur = get(i); tot = max(tot, cur[0] + cur[1]); } int i = 0; while (i < n) { vector <int> cur = get(i); if (cur[0] + cur[1] != tot) { if (cur[0] == 0 && cur[1] == 0) return i; ++i; } int L = i, R = n; while (L < R) { int mid = L + R + 1 >> 1; if (get(mid) == get(i)) L = mid; else R = mid - 1; } i = L + 1; } assert(0); } // //int main() { // cin >> n; // // g.resize(n); // for(int i = 0; i < n; i++) { // cin >> g[i]; // if(g[i] < 1) { // cerr << "Invalid rank " << g[i] << " at index " << i << endl; // exit(0); // } // } // // int max_rank = *max_element(g.begin(), g.end()); // // rank_count.resize(max_rank + 1, vector<int>(n + 1, 0)); // for(int r = 0; r <= max_rank; r++) { // for(int i = 1; i <= n; i++) { // rank_count[r][i] = rank_count[r][i - 1]; // if(g[i - 1] == r) // rank_count[r][i]++; // } // } // // for(int i = 0; i <= n; i++) // for(int r = 1; r <= max_rank; r++) // rank_count[r][i] += rank_count[r - 1][i]; // // int res = find_best(n); // cout << res << endl << "Query count: " << query_count << endl; // // return 0; //}

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:65:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |             int mid = L + R + 1 >> 1;
      |                       ~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...