Submission #741198

#	Time	Username	Problem	Language	Result	Execution time	Memory
741198		Charizard2021	The Big Prize (IOI17_prize)	C++17	Compilation error	0 ms	0 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
map<int, pair<int, int> > mp;
pair<int, int> Ask(int x){
	if(mp.find(x) != mp.end()){
        return mp[x];
    }
	auto q = ask(x);
	return mp[x] = make_pair<int, int>(q[0], q[1]);
}
int find_best(int n) {
	if(n <= 5000){
		for(int i = 0; i < n; i++) {
			vector<int> ans = ask(i);
			if(ans[0] + ans[1] == 0){
				return i;
            }
		}
	}
	vector<int> cur;
	for(int i = 0; i <= 500; i++){
		cur.push_back(((n-1) * i) / 500);
	}
	int value1 = 0;
	for(int i = 0; i < cur.size(); i++){
		pair<int, int> value2 = Ask(cur[i]);
		value1 = max(value1, value2.first + value2.second);
	}
	auto check = [&](int x){
		pair<int, int> value2 = Ask(x);
		return value2.first + value2.second != value1;
	};
	for(int i =0 ; i < n; i++){
		if(check(i)){
			pair<int, int> value2 = Ask(i);
			if(value2.first + value2.second == 0){
                return i;
            }
		}
		else{
			auto works = [&](int x, int y){
				if(check(y)) return true;
				auto value2 = Ask(x).second;
				auto q = Ask(y).second;
				return value2 != q;
			};
			int low = i + 1;
			int high = n + 100;
			for(auto &j : cur){
				if(j > i && works(i, j)){
					high = j;
					break;
				}
				low = max(low, j);
			}
			while(low != high){
				int mid = (low + high) / 2;
				if(works(i, mid)) high = mid;
				else low = mid + 1;
			}
			i = low - 1;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'std::pair<int, int> Ask(int)':
prize.cpp:10:47: error: cannot bind rvalue reference of type 'int&&' to lvalue of type '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'}
   10 |  return mp[x] = make_pair<int, int>(q[0], q[1]);
      |                                               ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from prize.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:567:21: note:   initializing argument 1 of 'constexpr std::pair<typename std::__strip_reference_wrapper<typename std::decay<_Tp>::type>::__type, typename std::__strip_reference_wrapper<typename std::decay<_Tp2>::type>::__type> std::make_pair(_T1&&, _T2&&) [with _T1 = int; _T2 = int; typename std::__strip_reference_wrapper<typename std::decay<_Tp2>::type>::__type = int; typename std::__strip_reference_wrapper<typename std::decay<_Tp>::type>::__type = int]'
  567 |     make_pair(_T1&& __x, _T2&& __y)
      |               ~~~~~~^~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:26:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < cur.size(); i++){
      |                 ~~^~~~~~~~~~~~
prize.cpp:21:14: warning: control reaches end of non-void function [-Wreturn-type]
   21 |  vector<int> cur;
      |              ^~~