Submission #122726

#TimeUsernameProblemLanguageResultExecution timeMemory
122726SirCenessThe Big Prize (IOI17_prize)C++14
20 / 100
96 ms2724 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; int tmp[200005]; 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; } ans[0] = anslar[k].first; ans[1] = anslar[k].second; return ans; } int find_best(int size){ n = size; for (int i = 0; i < size; i++) arr[i] = i; for (int i = 0; i < n; i++) anslar[i] = mp(-1, -1); srand(time(0)); maxx = 0; for (int i = 0; i < min(50, n); i++){ vector<int> ans = get(rand()%n); maxx = max(ans[0] + ans[1], maxx); } //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); while (ans[0] + ans[1] != maxx && l < m){ m--; ans = get(m); } if (l == m) break; if (ans[0] > i) r = m-1; else l = m; } //cout << "find: " << l << endl; vector<int> ans = get(l); if (ans[0] + ans[1] == maxx) l++; if (l >= n) continue; ans = get(l); while (ans[0] + ans[1] != maxx){ l++; if (l >= n) break; ans = get(l); } } //cout << "size: " << vec.size() << endl; return soncevap; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...