oj.uz

Submission #137545

# Submission time Handle Problem Language Result Execution time Memory
137545 2019-07-28T06:24:15 Z Mahdi_Jfri The Big Prize (IOI17_prize) C++14
0 / 100
 16 ms 9976 KB 
#include "prize.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back

const int maxn = 2e5 + 20;

vector<int> res[maxn] , candid;

int mx;

vector<int> reval(int k)
{
	if(!res[k].empty())
		return res[k];

	res[k] = ask(k);
	while(res[k][0] + res[k][1] > mx) cout << 1/0;
	return res[k];
}

void solve(int l , int r)
{
	while(l < r)
	{
		auto tmp = reval(l);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(l++);
		else
			break;
	}
	while(l < r)
	{
		r--;
		auto tmp = reval(r);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(r);
		else
			break;
	}

	if(l >= r)
		return;

	reval(l); reval(r);
	if(res[r][0] - res[l][0] == 0)
		return;

	int m = (l + r) / 2;
	solve(m , r + 1);
	solve(l , m);
}

int find_best(int n)
{
	if(n <= 5000)
	{
		for(int i = 0; i < n; i++) {
			std::vector<int> res = ask(i);
			if(res[0] + res[1] == 0)
				return i;
		}
	}

	for(int i = 0; i < 1000; i++)
	{
		vector<int> tmp = reval(i);
		mx = max(mx , tmp[0] + tmp[1]);
	}

	solve(0 , n);

	for(auto x : candid)
	{
		auto tmp = reval(x);
		if(tmp[0] + tmp[1] == 0)
			return x;
	}
	return -85;
}

Compilation message

prize.cpp: In function 'std::vector<int> reval(int)':
prize.cpp:21:45: warning: division by zero [-Wdiv-by-zero]
  while(res[k][0] + res[k][1] > mx) cout << 1/0;
                                            ~^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 9960 KB Execution killed with signal 4 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Runtime error 13 ms 9976 KB Execution killed with signal 4 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -