Submission #316118

#	Time	Username	Problem	Language	Result	Execution time	Memory
316118		MrDomino	The Big Prize (IOI17_prize)	C++14	Compilation error	0 ms	0 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"

using namespace std;

mt19937 rng((long long) (new char));
const int N = 200000 + 7;
vector<int> ret[N];
int sol = -1;

vector<int> get(int i) {
  if (ret[i].empty()) {
    ret[i] = ask(i);
    if (ret[i][0] == 0 && ret[i][1] == 0) {
      sol = i;
    }
  }
  return ret[i];
}

void after(int n, int pos) {
  int cnt = 0, go = pos + 1;
  while (go < n) {
    int lo = go, hi = n - 1, id = -1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (get(mid)[0] + get(mid)[1] != get(pos)[0] + get(pos)[1]) {
        if (get(mid)[0] == get(pos)[0] + cnt) {
          id = mid;
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      } else {
        id = mid;
        hi = mid - 1;
      }
    }
    if (id == -1) {
      break;
    }
    if (sol != -1) {
      return;
    }
    cnt++;
    go = id + 1;
  }
}

void before(int n, int pos) {
  int cnt = 0, go = pos - 1;
  while (go >= 0) {
    int lo = 0, hi = go, id = -1;
    while (lo <= hi) {
      int mid = (lo + hi) / 2;
      if (get(mid)[0] + get(mid)[1] != get(pos)[0] + get(pos)[1]) {
        if (get(mid)[1] == get(pos)[1] + cnt) {
          lo = mid + 1;
          id = mid;
        } else {
          hi = mid - 1;
        }
      } else {
        id = mid;
        lo = mid + 1;
      }
    }
    if (id == -1) {
      break;
    }
    if (sol != -1) {
      return;
    }
    cnt++;
    go = id - 1;
  }
}

int find_best(int n) {
  vector<int> ord;
  for (int i = 0; i < n; i++) {
    ord.push_back(i);
  }
  shuffle(ord.begin(), ord.end());
  while ((int) ord.size() > 500) {
    ord.pop_back();
  }
  int big = 0, pos = -1;
  for (auto &i : ord) {
    big = max(big, get(i)[0] + get(i)[1]);
  }
  for (auto &i : ord) {
    if (big == get(i)[0] + get(i)[1]) {
      pos = i;
    }
  }
  assert(pos != -1);
  if (sol != -1) {
    return sol;
  }
  after(n, pos);
  if (sol != -1) {
    return sol;
  }
  before(n, pos);
  assert(sol != -1);
  return sol;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:84:33: error: no matching function for call to 'shuffle(std::vector<int>::iterator, std::vector<int>::iterator)'
   84 |   shuffle(ord.begin(), ord.end());
      |                                 ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from prize.cpp:1:
/usr/include/c++/9/bits/stl_algo.h:3786:5: note: candidate: 'template<class _RAIter, class _UGenerator> void std::shuffle(_RAIter, _RAIter, _UGenerator&&)'
 3786 |     shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      |     ^~~~~~~
/usr/include/c++/9/bits/stl_algo.h:3786:5: note:   template argument deduction/substitution failed:
prize.cpp:84:33: note:   candidate expects 3 arguments, 2 provided
   84 |   shuffle(ord.begin(), ord.end());
      |                                 ^