Custom binary search using std::lower_bound over used-defined iterators.

pipe.cc

#include <cstdio>
#include <algorithm>
#include <iterator>
#include <vector>

using namespace std;

struct TestCase {
  int N;
  int K;
  vector<int> sizes;

  struct iterator : public ::iterator<random_access_iterator_tag, int> {
    TestCase* test;
    int pieceLength;

    iterator(): test() {}
    iterator(TestCase* test, int pieceLength): test(test), pieceLength(pieceLength) {}

    int operator*() const {
      if (pieceLength == 0) {
        return 1;
      }
      int count = 0;
      for (int i = 0; i < test->sizes.size(); ++i) {
        count += test->sizes[i] / pieceLength;
      }
      return count >= test->K;
    }

    iterator& operator++() {
      --pieceLength;
      return *this;
    }

    iterator operator++(int) {
      iterator temp(*this);
      --pieceLength;
      return temp;
    }

    iterator& operator+=(int n) {
      pieceLength -= n;
      return *this;
    }
  };
};

int operator-(const TestCase::iterator& a, const TestCase::iterator& b) {
  return b.pieceLength - a.pieceLength;
}

int main() {
  int T;
  scanf("%d", &T);
  for (int t = 0; t < T; ++t) {
    TestCase test;
    scanf("%d %d", &test.N, &test.K);
    test.sizes.resize(test.N);
    for (int i = 0; i < test.N; ++i) {
      scanf("%d", &test.sizes[i]);
    }
    TestCase::iterator start(&test, 1e7);
    TestCase::iterator end(&test, -1);
    TestCase::iterator it = std::lower_bound(start, end, 1);
    printf("%d\n", it.pieceLength);
  }
}