Submission #566599

#	Time	Username	Problem	Language	Result	Execution time	Memory
566599		sofapuden	The Big Prize (IOI17_prize)	C++14	0 / 100	3 ms	296 KiB

prize

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

using namespace std;

int ret = -1;
int ll = 0, rr = 0;
int N;
set<int> am;

vector<int> g(int x){
	vector<int> q = ask(x);
	if(q ==vector<int>(2,0))ret = x;
	am.insert(q[0]+q[1]);
	return {q};
}
vector<int> p(int x){
	int l = 0, r = N-1;
	while(l <= r){
		int m = (l+r)>>1;
		vector<int> q = g(m);
		deque<vector<int>> QQ;
		QQ.push_front(q);
		int z = m-1;
		while(q[0]+q[1] != (*am.rbegin()) && ~z){
			q = g(z);
			QQ.push_front(q);
			z--;
		}
		if(q[0]+q[1] != (*am.rbegin())){
			if(QQ.size() > x)return QQ[x];
			else l = m+1;
		}
		else{
			if(q[0] <= x && q[0]+QQ.size() > x)return QQ[x-q[0]];
			if(q[0] > x){
				r = z-1;
			} else {
				l = m+1;
			}
		}
	}
	return {0};
}
vector<int> h(int x){
	int l = 0, r = *next(am.rbegin())-1;
	while(l <= r){
		int m = (l+r)>>1;
		vector<int> q = p(m);
		if(q[0] == x)return q;
		if(q[0] > x){
			r = m-1;
		} else {
			l = m+1;
		}
	}
	return {0};
}
vector<int> f(int x){
	int l = 0, r = *am.begin();
	while(l <= r){
		int m = (l+r)>>1;
		vector<int> q = h(m);
		if(q[0] == x)return q;
		if(q[0] > x){
			r = m-1;
		} else {
			l = m+1;
		}
	}
	return {0};
}

int find_best(int n) {
	N = n;
	for(int i = 0; i <= sqrt(n); ++i){
		g(i);
	}
	if(ret != -1)return ret;
	for(int i = 0; i <= sqrt(*am.rbegin()); ++i){
		p(i);
	}
	if(ret != -1)return ret;
	for(int i = 0; i <= sqrt(*next(am.rbegin())); ++i){
		h(i);
	}
	if(ret != -1)return ret;
	f(0);
	return ret;
}

Compilation message (stderr)

prize.cpp: In function 'std::vector<int> p(int)':
prize.cpp:31:17: warning: comparison of integer expressions of different signedness: 'std::deque<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |    if(QQ.size() > x)return QQ[x];
      |       ~~~~~~~~~~^~~
prize.cpp:35:35: warning: comparison of integer expressions of different signedness: 'std::deque<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |    if(q[0] <= x && q[0]+QQ.size() > x)return QQ[x-q[0]];

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