제출 #1205274

#제출 시각아이디문제언어결과실행 시간메모리
1205274shadowcoderThe Big Prize (IOI17_prize)C++20
90 / 100
21 ms2172 KiB
#include "prize.h" #include <bits/stdc++.h> using namespace std; const int maxn = 200005; bool asked[maxn]; int ansL[maxn], ansR[maxn]; void query(int pos) { if (asked[pos] == true) return; asked[pos] = true; vector<int> curr = ask(pos); ansL[pos] = curr[0]; ansR[pos] = curr[1]; } const int SEARCH_TO = 500; int find_best(int n) { /*if (n <= 5000) { for (int i = 0; i < n; ++i) { query(i); if (ansL[i] + ansR[i] == 0) return i; } }*/ for (int i = 0; i < SEARCH_TO; ++i) { query(i); if (ansL[i] + ansR[i] == 0) return i; } int start = 0, better = 0; int maxSum = ansL[0] + ansR[0]; for (int i = 1; i < SEARCH_TO; ++i) { if (ansL[start] + ansR[start] < ansL[i] + ansR[i]) { start = i; maxSum = ansL[i] + ansR[i]; } } for (int i = 0; i < start; ++i) { if (ansL[i] + ansR[i] < ansL[start] + ansR[start]) { ++better; } } while (true) { //cout << start << " :: " << better << endl; int l = start + 1; int r = n - 1; while (l <= r) { int mid = (l + r) / 2; query(mid); //cout << l << " " << r << " " << mid << " :: " << ansL[mid] << " " << ansR[mid] << endl; if (ansL[mid] + ansR[mid] == 0) return mid; if (ansL[mid] + ansR[mid] < maxSum) { r = mid - 1; } else { if (ansL[mid] > better) r = mid - 1; else l = mid + 1; } } int blockEnd = r; //cout << "now " << blockEnd << endl; for (int i = blockEnd + 1; i < n; ++i) { query(i); if (ansL[i] + ansR[i] == 0) return i; if (ansL[i] + ansR[i] == maxSum) { start = i; break; } ++better; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...