제출 #565888

#제출 시각아이디문제언어결과실행 시간메모리
565888hoanghq2004커다란 상품 (IOI17_prize)C++14
20 / 100
1133 ms6448 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]); } map <int, map <int, int>> mp; function <int(int, int)> divide = [&](int L, int R) { if (L > R) return -1; int mid = L + R >> 1; for (auto [_, S]: mp) { auto rgt = S.upper_bound(mid); auto lft = rgt; if (rgt != S.end() && lft != S.begin()) { --lft; if (lft -> second == rgt -> second) return -1; } } if (get(mid)[0] + get(mid)[1] == 0) return mid; mp[get(mid)[0] + get(mid)[1]][mid] = get(mid)[0]; int ans = divide(L, mid - 1); if (ans == -1) ans = divide(mid + 1, R); return ans; }; return divide(0, n - 1); } // //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:59:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |         int mid = L + R >> 1;
      |                   ~~^~~
prize.cpp:60:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |         for (auto [_, S]: mp) {
      |                   ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...