Submission #1139085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139085		fryingduc	커다란 상품 (IOI17_prize)	C++20	20 / 100	4 ms	5124 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else 
#define debug(...)
#endif


mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
  assert(l <= r);
  return uniform_int_distribution<int> (l, r)(rng);
}
const int maxn = 2e5 + 5;
vector<int> que[maxn];
int cnt_asks;
vector<int> abc(int i) {
  ++cnt_asks;
  if(!que[i].empty()) {
    return que[i];
  } else {
    return que[i] = ask(i);
  }
}
int find_best(int n) {
  int mx = 0;
  for(int ite = 0; ite < 25; ++ite) {
    int p = rand(0, n - 1);
    vector<int> cur_ask = abc(p);
    mx = max(mx, cur_ask[0] + cur_ask[1]);
  }
  debug(mx, mx + mx * 20);
  assert(mx <= 420);
  int spec = 0;
  for(int i = 0; i < n; ++i) {
    debug(cnt_asks, i, spec);
    vector<int> cur_ask = abc(i);
    if(cur_ask[0] + cur_ask[1] != mx) {
      ++spec;
      if(cur_ask[0] == 0 and cur_ask[1] == 0) {
        return i;
      }
      continue;
    }
    int l = i + 1, r = n - 1, nxt = i;
    while(l <= r) {
      int mid = (l + r) >> 1;
      vector<int> he = abc(mid);
      if(he == cur_ask) {
        nxt = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    i = nxt;
  }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80