Submission #549328

#	Time	Username	Problem	Language	Result	Execution time	Memory
549328		cig32	The Big Prize (IOI17_prize)	C++17	20 / 100	3085 ms	2076 KiB

prize

#include "prize.h"
 
 
 
 
#include <iostream>
#include <vector>
#include <algorithm>
#include "bits/stdc++.h"
 
using namespace std;
 
int find_best(int n);
std::vector<int> ask(int i);
 
static const int max_q = 5000;
static int n;
static int query_count = 0;
static vector<int> g;
static vector<vector<int> > rank_count;
 
 
 
mt19937 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
 
int find_best(int n) {
  
  if(n <= 5000) {
    for(int i=0; i<n; i++) {
      vector<int> res = ask(i);
      if(res[0] + res[1] == 0) {
        return i;
      }
    }
  }
  int res[n][2];
  for(int i=0; i<n; i++) {
    for(int j=0; j<2; j++) {
      res[i][j] = -1;
    }
  }
  int t = ceil(sqrt(n));
  vector<int> v;
  int goodcnt = 0;
  for(int i=0; i<t-100; i++) {
    int x;
    
    x = t * (i + (t - 1) + (100 * t) / (t - 100));
    if(x >= n) {
      
      while(1) {
        x = rnd(0, n - 1);
        if(res[x][0] == -1) break;
      }
 
    }
    vector<int> ok = ask(x);
    goodcnt = max(goodcnt, ok[0] + ok[1]);
    res[x][0] = ok[0], res[x][1] = ok[1];
    if(ok[0] + ok[1] == 0) {
      return x;
    }
    //cout << ok[0] + ok[1] << " ";
  }
  //cout << "\n";
  //cout << goodcnt << "\n";
  // solution idea: binary search
  // find all 'good' indices, one of them holds the big prize
  // 450 * log2(450) + C queries?
  vector<int> big;
  for(int i=0; i<n; i++) {
    if(res[i][0] != -1 && res[i][0] + res[i][1] == goodcnt) {
      big.push_back(i);
      //cout << i << " ";
    }
  }
  //cout << "\n";
  //cout << big.size() << "\n";
  queue<pair<pair<int, int>, int> > ranges;
  if(big[0] != 0 && res[big[0]][0] > 0) ranges.push({{0, big[0] - 1}, res[big[0]][0]});
  for(int i=1; i<big.size(); i++) {
    if(big[i-1] + 1 == big[i]) continue;
    if(res[big[i]][0] - res[big[i-1]][0] > 0) ranges.push({{big[i-1] + 1, big[i] - 1}, res[big[i]][0] - res[big[i-1]][0]});
  }
  if(big[big.size() - 1] != n - 1 && res[big[big.size() - 1]][1] > 0) ranges.push({{big[big.size() - 1] + 1, n - 1}, res[big[big.size() - 1]][1]});
  //cout << ranges.size() << "\n";
  while(ranges.size()) {
    pair<pair<int, int>, int> f = ranges.front();
    //cout << "split ["  << f.first.first <<", "<<f.first.second <<"]: " <<f.second << "\n";
    ranges.pop();
    if(f.second * 2 >= f.first.second - f.first.first + 1) {
      // just query each one, at most 2 * 450 here
      for(int i = f.first.first; i <= f.first.second; i++) {
        vector<int> qwq = ask(i);
        if(qwq[0] + qwq[1] == 0) return i;
      }
    }
    else {
      int mid = (f.first.first + f.first.second) >> 1;
      vector<int> qwq;
      while(1) {
        if(res[mid][0] == -1) {
          qwq = ask(mid);
          res[mid][0] = qwq[0];
          res[mid][1] = qwq[1];
          if(qwq[0] + qwq[1] == 0) return mid;
          if(qwq[0] + qwq[1] == goodcnt) break;
        }
        mid = rnd(f.first.first, f.first.second);
      }
      /*
      cout << "lchild " <<(f.first.first == 0 ? 0 : res[f.first.first - 1][0]) << ", ";
      cout << "rchild "<<(f.first.second == n - 1 ? 0 : res[f.first.second + 1][1])<<"\n";
      cout << "results "<<qwq[0] <<" " <<qwq[1] << "\n";
      */
      if(f.first.first <= mid - 1 && qwq[0] - (f.first.first == 0 ? 0 : res[f.first.first - 1][0]) > 0) {
        ranges.push({{f.first.first, mid - 1}, qwq[0] - (f.first.first == 0 ? 0 : res[f.first.first - 1][0])});
      }
      if(mid + 1 <= f.first.second && qwq[1] - (f.first.second == n - 1 ? 0 : res[f.first.second + 1][1]) > 0) {
        ranges.push({{mid + 1, f.first.second}, qwq[1] - (f.first.second == n - 1 ? 0 : res[f.first.second + 1][1])});
      }
    }
  }
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |   for(int i=1; i<big.size(); i++) {
      |                ~^~~~~~~~~~~
prize.cpp:46:15: warning: control reaches end of non-void function [-Wreturn-type]
   46 |   vector<int> v;
      |               ^
prize.cpp: At global scope:
prize.cpp:18:12: warning: 'query_count' defined but not used [-Wunused-variable]
   18 | static int query_count = 0;
      |            ^~~~~~~~~~~
prize.cpp:17:12: warning: 'n' defined but not used [-Wunused-variable]
   17 | static int n;
      |            ^

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