Submission #290318

#TimeUsernameProblemLanguageResultExecution timeMemory
290318A02The Big Prize (IOI17_prize)C++14
0 / 100
31 ms22760 KiB
#include <bits/stdc++.h> #include "prize.h" using namespace std; vector<vector<int> > asked; vector<int> ask2(int i){ if (asked[i][0] == -1){ asked[i] = ask(i); } return asked[i]; } int find_best(int n) { asked = vector<vector<int> > (n, vector<int> (2, -1)); if (n <= 5000){ for (int i = 0; i < n; i++){ vector<int> r = ask(i); if (r[0] == 0 && r[1] == 0){ return i; } } } int small_count = 0; for (int i = 0; i < 500; i++){ int low = 0; int high = n; for (int a = 0; a < 9; a++){ small_count = max(small_count, ask2((low + high) / 2)[0] + ask2((low + high) / 2)[1]); if (i & (1 << 8)){ low = (low + high) / 2; } else { high = (low + high) / 2; } } } vector<int> small_pos (small_count, -1); for (int p = 0; p < small_count; p++){ //cout << 'p' << ' ' << p << endl; int low = 0; int high = n; int left_elements = 0; //pth small element in [0, n). while (high != low + 1){ int mid = (low + high) / 2; //cout << low << ' ' << high << ' ' << left_elements << endl; while(ask2(mid)[0] + ask2(mid)[1] != small_count && mid - 1 >= low){ mid--; } int m_original = (low + high) / 2; if (m_original != mid){ if (ask2(mid)[0] + ask2(mid)[1] != small_count){ int width = m_original - low; if (p <= left_elements + width){ high = m_original; } else { low = m_original; left_elements += width; } } else { int extra = m_original - mid; int left_of_mid_elements = ask2(m_original)[0] + extra - 1; if (left_of_mid_elements >= p){ high = m_original; } else { low = m_original; left_elements = left_of_mid_elements; } } } else { int left_of_mid_elements = ask2(mid)[0]; if (left_of_mid_elements >= p){ high = mid; } else { low = mid; left_elements = left_of_mid_elements; } } } small_pos[p] = low; if (ask2(low)[0] + ask2(low)[1] == 0){ return low; } } }

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:46:43: warning: control reaches end of non-void function [-Wreturn-type]
   46 |     vector<int> small_pos (small_count, -1);
      |                                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...