Submission #741199

#	Time	Username	Problem	Language	Result	Execution time	Memory
741199		Charizard2021	The Big Prize (IOI17_prize)	C++17	100 / 100	60 ms	588 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(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 '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;
      |              ^~~

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