제출 #565336

#제출 시각아이디문제언어결과실행 시간메모리
565336hoanghq2004커다란 상품 (IOI17_prize)C++14
20 / 100
84 ms11524 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); int res = -1; auto get = [&](int i) { if (ans[i].size()) return ans[i]; ans[i] = ask(i); if (ans[i][0] + ans[i][1] == 0) { // assert(0); res = i; } return ans[i]; }; auto ok = [&](int i) { return (get(i)[0] + get(i)[1] != tot); }; 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]); } get(0), get(n - 1); function <void(int, int, int)> divide = [&](int L, int R, int cnt) { if (L > R || cnt <= 0 || res != -1) return; int m1 = L + R >> 1; int m2 = m1 + 1; while (m1 >= L && ok(m1)) --m1; while (m2 <= R && ok(m2)) ++m2; divide(L, m1, get(m1)[0] - get(L)[0]); divide(m2, R, get(m2)[1] - get(R)[1]); }; divide(0, n - 1, tot); return res; } // //int main() { //// freopen("test.inp", "r", stdin); // cin >> n; // // g.resize(n); // int id = rand() % n; //// cout << id << "aaa\n"; // for(int i = 0; i < n; i++) { // cin >> g[i]; //// if (i == id) g[i] = 1; //// else g[i] = 2; // 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 lambda function:
prize.cpp:67:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |         int m1 = L + R >> 1;
      |                  ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...