제출 #122820

#제출 시각아이디문제언어결과실행 시간메모리
122820SirCeness커다란 상품 (IOI17_prize)C++14
96.04 / 100
66 ms2728 KiB
#include <bits/stdc++.h> #define pb push_back #define mp make_pair #include "prize.h" using namespace std; typedef long long ll; int arr[200005]; int n; pair<int, int> anslar[200005]; int maxx; int soncevap = -1; // 22 vector<int> get(int k){ //cout << "get(" << k << ")" << endl; vector<int> ans(2); if (anslar[k].first == -1){ ans = ask(k); anslar[k] = mp(ans[0], ans[1]); if (ans[0] + ans[1] == 0){ soncevap = k; //cout << "cevabim: " << k << endl; //cout << ans[0] << " - " << ans[1] << endl; } } ans[0] = anslar[k].first; ans[1] = anslar[k].second; //cout << "return " << ans[0] << ", " << ans[1] << endl; return ans; } int find_best(int size){ n = size; for (int i = 0; i < size; i++) arr[i] = i; for (int i = 0; i < 200005; i++) anslar[i] = mp(-1, -1); maxx = 1; for (int i = 0; i <= min(500, n); i++){ vector<int> ans = get(i); if(soncevap != -1) return soncevap; maxx = max(ans[0] + ans[1], maxx); //if (maxx > sqrt(sqrt(n))) break; } //cout << "maxx: " << maxx << endl; for (int i = 0; i < maxx; i++){ //cout << "i: " << i << endl; int l = 0; int r = n-1; while (l < r){ int m = (l+r+1)/2; vector<int> ans = get(m); if(soncevap != -1) return soncevap; while (ans[0] + ans[1] != maxx && l < m){ m--; ans = get(m); if(soncevap != -1) return soncevap; } if (l == m) break; if (ans[0] > i) r = m-1; else l = m; } //cout << "find: " << l << endl; vector<int> ans = get(l); if(soncevap != -1) return soncevap; if (ans[0] + ans[1] == maxx) l++; if (l >= n) continue; while (anslar[l].first != -1 && l < n){ if (anslar[l].first + anslar[l].second == maxx) break; l++; } if (l >= n) continue; ans = get(l); if(soncevap != -1) return soncevap; } //cout << "size: " << vec.size() << endl; assert(soncevap != -1); return soncevap; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...