oj.uz

Submission #137750

# Submission time Handle Problem Language Result Execution time Memory
137750 2019-07-28T09:24:34 Z Mahdi_Jfri The Big Prize (IOI17_prize) C++14
0 / 100
 20 ms 10136 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;

bool found;
 
vector<int> reval(int k)
{
	if(!res[k].empty())
		return res[k];
 
	res[k] = ask(k);
	if(res[k][0] + res[k][1] == 0)
		found = 1;
	return res[k];
}
 
void solve(int l , int r)
{
	if(found)
		return;
	while(l < r)
	{
		if(found)
			return;
		auto tmp = reval(l);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(l++);
		else
			break;
	}
	if(found)
		return;
	while(l < r)
	{
		if(found)
			return;
		r--;
		auto tmp = reval(r);
		if(tmp[0] + tmp[1] != mx)
			candid.pb(r);
		else
			break;
	}
	if(found)
		return;
 
	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 < 550; 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;
	}
	cout << 1/0;
	return -85;
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:95:11: warning: division by zero [-Wdiv-by-zero]
  cout << 1/0;
          ~^~

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4984 KB Output is correct
2 Correct 11 ms 5024 KB Output is correct
3 Correct 12 ms 4984 KB Output is correct
4 Correct 12 ms 4984 KB Output is correct
5 Correct 14 ms 5112 KB Output is correct
6 Runtime error 20 ms 10136 KB Execution killed with signal 4 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5164 KB Output is correct
2 Correct 12 ms 5032 KB Output is correct
3 Correct 12 ms 5056 KB Output is correct
4 Correct 14 ms 4984 KB Output is correct
5 Correct 12 ms 5112 KB Output is correct
6 Runtime error 20 ms 10104 KB Execution killed with signal 4 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -