제출 #290330

#제출 시각아이디문제언어결과실행 시간메모리
290330A02커다란 상품 (IOI17_prize)C++14
20 / 100
68 ms22776 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); //cout << small_count << endl; for (int p = 0; p < small_count; p++){ //cout << endl; //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){ //cout << 'a' << endl; if (ask2(mid)[0] + ask2(mid)[1] != small_count){ //cout << 'b' << endl; int width = m_original - low; if (p <= left_elements + width){ high = m_original; } else { low = m_original; left_elements += width; } } else { //cout << 'c' << endl; //cout << mid << ' ' << m_original << endl; int extra = m_original - mid; int left_of_mid_elements = ask2(mid)[0] + extra - 1; //cout << ' ' << left_of_mid_elements << endl; 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; //cout << p << ' ' << low << endl; if (ask2(low)[0] + ask2(low)[1] == 0){ return low; } } }

컴파일 시 표준 에러 (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...