제출 #1326272

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1326272		apxo	커다란 상품 (IOI17_prize)	C++20	20 / 100	28 ms	5352 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;
const int B = 700;
vector<int> que[maxn];
int cnt_asks;

vector<int> abc(int i) {
  if(!que[i].empty()) {
    return que[i];
  } else {
    ++cnt_asks;
    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]);
  }
  int ptr = 0;
  abc(ptr);
  if (que[ptr][0] + que[ptr][1] == 0) return ptr;
  while (ptr < n) {
    while (ptr < n) {
      vector<int> xx = abc(ptr);
      if (xx[0] + xx[1] == 0) return ptr;
      if (xx[0] + xx[1] == mx) break;
      ++ptr;
    }
//    debug(ptr);
    int x = min(n - 1, ptr + B);
    while (x > ptr) {
      vector<int> cur = abc(x);
      if (cur[0] + cur[1] == 0) return x;
      if (cur[0] + cur[1] < mx) --x;
      else break;
    }
    if (x == ptr) {
      ptr += B + 1;
      continue;
    }
    vector<int> cur = abc(x);
    vector<int> cur_ask = abc(ptr);
//    debug(x, cur);
    if (cur[0] - cur_ask[0]) {
      int l = ptr + 1, r = n - 1, nxt = ptr;
      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;
        }
      }
      ptr = nxt + 1;
    } else {
      ptr = x;
    }
  }
  int spec = 0;
//  for(int i = ptr; i < n; ++i) {
////    debug(cnt_asks, i, spec);
//    vector<int> cur_ask = abc(i);
//    if(cur_ask[0] == 0 and cur_ask[1] == 0) {
//      return i;
//    }
//    if(cur_ask[0] + cur_ask[1] != mx) {
//      ++spec;
//      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;
//  }
  return -1;
}

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