Submission #833910

#	Time	Username	Problem	Language	Result	Execution time	Memory
833910		Josia	The Big Prize (IOI17_prize)	C++17	20 / 100	52 ms	336 KiB

prize

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






int getNumBetter(vector<int> x) {
	return x[0]+x[1];
}


int find_best(int n) {
	int numBetter = 0;
	int ind = 0;

	for (int i = 0; i<min(n, 500); i++) {
		int hereBetter = getNumBetter(ask(i));
		if (hereBetter > numBetter) {
			numBetter = hereBetter;
			ind = i;
		}
	}

	set<int> candidates;
	for (int i=0; i<ind; i++) candidates.insert(i);

	int pos = ind;

	int oldL=-1, oldR=-1;
	while (true) {
		int l = pos+1, r = n-1;
		while (l<r) {
			int m = (l+r)/2;
			vector<int> ans = ask(m);

			if (getNumBetter(ans) < numBetter) {
				r = m;
				continue;
			}

			if (ans[1] < numBetter-candidates.size()) {
				r = m;
			}
			else l = m+1;
		}

		int pos = l;

		while (pos < n && getNumBetter(ask(pos)) < numBetter) {
			candidates.insert(pos);
			pos++;
		}

		if (candidates.size() == numBetter) break;

	}

	for (int i: candidates) {
		if (getNumBetter(ask(i)) == 0) return i;
	}

	assert(0);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:44:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    if (ans[1] < numBetter-candidates.size()) {
prize.cpp:57:25: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |   if (candidates.size() == numBetter) break;
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
prize.cpp:32:6: warning: unused variable 'oldL' [-Wunused-variable]
   32 |  int oldL=-1, oldR=-1;
      |      ^~~~
prize.cpp:32:15: warning: unused variable 'oldR' [-Wunused-variable]
   32 |  int oldL=-1, oldR=-1;
      |               ^~~~

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