제출 #102331

#제출 시각아이디문제언어결과실행 시간메모리
102331bert30702커다란 상품 (IOI17_prize)C++17
20 / 100
20 ms632 KiB
#include <bits/stdc++.h> #include "prize.h" #define pii pair<int, int> #define F first #define S second using namespace std; unordered_map<int, pii> mp; //vector<int> ask(int p) { // cout << p << endl; // int a, b; cin >> a >> b; // return {a, b}; //} int cnt = 0; pii query(int p) { if(mp.find(p) != mp.end()) return mp[p]; cnt ++; // assert(cnt < 10000); vector<int> v = ask(p); return mp[p] = {v[0], v[1]}; } int find_best(int n) { srand(time(0)); int mx = 0; set<int> Yeee; for(int i = 0; i < min(n, 50); i ++) { int p = rand() % n; pii r = query(p); mx = max(mx, r.F + r.S); } vector<pair<int, pii> > OK; for(int i = 0; i < n; i ++) { pii p = query(i); if(p.F + p.S == mx) { int l = i + 1, r = n; while(l != r) { int m = l + r >> 1; pii v = query(m); if(v.F == p.F and v.S == p.S) { i = m; l = i + 1; } else { r = m; } } if(l < n) { OK.push_back({l, query(l)}); } // i = l; } else { OK.push_back({i, p}); } } assert(OK.size() <= sqrt(n)); pii ans = {1 << 30, -1}; for(auto it: OK) ans = min(ans, {it.S.F + it.S.S, it.F}); assert(OK.size()); return ans.S; } //main () { // cout << find_best(7); //}

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

prize.cpp: In function 'int find_best(int)':
prize.cpp:36:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m = l + r >> 1;
             ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...