제출 #289168

#제출 시각아이디문제언어결과실행 시간메모리
289168Touubs커다란 상품 (IOI17_prize)C++17
95.08 / 100
71 ms5496 KiB
#include "prize.h" using namespace std; #include <bits/stdc++.h> int non_worst_box_cnt = 0; bool notworst(vector<int> res) { return (res[0] + res[1] != non_worst_box_cnt); } bool best(vector<int> res) { return (res[0] + res[1] == 0); } bool contains(int a, vector<int> ares, int b, vector<int> bres) { //cout << " checking between " << a << " and " << b << "\n"; return bres[0] != ares[0]; } vector<vector<int>> askcache(200000); vector<bool> asked(200000); vector<int> ask_(int i) { //cout << "asking " << i << "\n"; if (!asked[i]) { asked[i] = true; askcache[i] = ask(i); } return askcache[i]; } int binary_search(int min, int max) { if (min > max) return -1; if (min == max) { if (best(ask_(min))) return min; return -1; } int mid = (min + max) / 2; auto minres = ask_(min); if (notworst(minres)) { if (best(minres)) { return min; } return binary_search(min + 1, max); } auto maxres = ask_(max); if (notworst(maxres)) { if (best(maxres)) { return max; } return binary_search(min, max - 1); } auto midres = ask_(mid); if (notworst(midres)) { if (best(midres)) { return mid; } if (min + 2 < max) return std::max(binary_search(min, mid), binary_search(mid, max)); else return std::max(binary_search(min, mid), binary_search(mid + 1, max)); } int opt = -1; if (contains(min, minres, mid, midres)) { opt = std::max(opt, binary_search(min, mid)); } if (contains(mid, midres, max, maxres)) { if (min + 2 < max) opt = std::max(opt, binary_search(mid, max)); else opt = std::max(opt, binary_search(mid + 1, max)); } return opt; } int find_best(int n) { for (int i = 0; i < 480 && i < n; i++) { auto v = ask_(i); int va = v[0]; int vb = v[1]; non_worst_box_cnt = max(non_worst_box_cnt, va + vb); } return binary_search(0, n - 1); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...