제출 #393507

#제출 시각아이디문제언어결과실행 시간메모리
393507JimmyZJX커다란 상품 (IOI17_prize)C++14
0 / 100
6 ms268 KiB
#include <iostream> #include <fstream> #include <algorithm> #include <cstring> #include <climits> #include <cassert> #include <tuple> #include <queue> #include <stack> #include <vector> #include <map> #include <set> #include <string> #include <unordered_set> #include <unordered_map> #include <numeric> using namespace std; typedef long long LL; typedef vector<int> Vi; typedef vector<LL> VL; typedef vector<bool> Vb; typedef vector<vector<int>> Vii; #define forR(i, n) for (int i = 0; i < (n); i++) Vi ask(int i); int cntV = 0, N; int getLeftNonVCnt(int i) { int c = 0; while (true) { if (i >= N) return N - cntV; Vi rs = ask(i); if (rs[0] + rs[1] == N - cntV) { // is a V node return rs[0] - c; } else { i++; c++; } } } int find_best(int n) { N = n; if (n <= 5000) { forR(i, n) { Vi rs = ask(i); if (rs[0] == 0 && rs[1] == 0) return i; } } else { cntV = 0; forR(i, 500) { Vi rs = ask(i); if (rs[0] == 0 && rs[1] == 0) return i; cntV = max(cntV, n - rs[0] - rs[1]); } int cntNotV = n - cntV; for (int t = 0; t < cntNotV; t++) { // goal: get the t-th non-V node int l = 0, r = n - 1; while (l < r) { int mid = (l + r) / 2; if (getLeftNonVCnt(mid + 1) >= t) { r = mid; } else { l = mid + 1; } } // l is the t-th non-V node Vi rs = ask(l); if (rs[0] == 0 && rs[1] == 0) return l; } return -1; } int l = 0, r = n - 1; while (l < r) { int mid = (l + r) / 2; Vi rs = ask(mid); if (rs[0] == rs[1]) return mid; if (rs[0] == 1) { r = mid - 1; } else { l = mid + 1; } } return l; } #ifdef TEST_LOCAL Vi _answer{ 2,2,1,2,2,2,2,2,2,2,2,2 }; Vi ask(int i) { int n = _answer.size(); assert(i >= 0 && i < n); int l = 0, r = 0; for (int j = 0; j < n; j++) { if (_answer[j] < _answer[i]) { if (j < i) l++; else r++; } } return Vi{ l, r }; } int main() { auto r = find_best(_answer.size()); return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...