oj.uz

Submission #72489

# Submission time Handle Problem Language Result Execution time Memory
72489 2018-08-26T08:31:20 Z Kmcode The Big Prize (IOI17_prize) C++14
0 / 100
 1000 ms 572 KB 
#include<bits/stdc++.h>
using namespace std;

//#include "prize.h"

#include <vector>

int find_best(int n);
std::vector<int> ask(int i);

namespace solver{
	map<int,pair<int,int> > mp;
	int fin;
	pair<int,int> query(int box){
		if(box==-1){
			return make_pair(0,-111);
		}
		if(mp.count(box))return mp[box];
		auto z=ask(box);
		if(z[0]==0&&z[1]==0){
			fin=box;
		}
		return mp[box]=make_pair(z[0],z[1]);
	}
	int mx;
	inline void dfs(int l,int r){
		int r_cn=query(r-1).first+query(r-1).second;
		int l_cn=query(l-1).first+query(l-1).second;
		mx=max(mx,r_cn);
		mx=max(mx,l_cn);
		while(r>l&&r_cn!=mx&&fin!=-1){
			if(l>=r)return;
			r_cn=query(r-1).first+query(r-1).second;
			if(r_cn==l_cn&&query(l-1).first==query(r-1).first)return;
			mx=max(mx,r_cn);
		}
		while(r>l&&l_cn!=mx&&fin!=-1){
			l++;
			if(l>=r)return;
			l_cn=query(l-1).first+query(l-1).second;
			if(r_cn==l_cn&&query(l-1).first==query(r-1).first)return;
			mx=max(mx,l_cn);
		}
		if(r<=l)return;
		if(fin!=-1)return;
		if(r_cn==l_cn&&query(l-1).first==query(r-1).first)return;
		if(query(r-1).first==0)return;
		if(l+1==r)return;
		if(rand()&1){
		if(fin!=-1)return;
		dfs(l,(l+r)>>1);
		if(fin!=-1)return;
		dfs((l+r)>>1,r);
		}
		else{
			if(fin!=-1)return;
		dfs((l+r)>>1,r);
			if(fin!=-1)return;
		dfs(l,(l+r)>>1);
		
		}
	
	}
	int find_best(int n) {
		fin=-1;
		dfs(0,n);
		return fin;
	}
}

int find_best(int n) {
	return solver::find_best(n);
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 516 KB Output is correct
4 Correct 3 ms 516 KB Output is correct
5 Correct 3 ms 516 KB Output is correct
6 Correct 2 ms 556 KB Output is correct
7 Correct 2 ms 572 KB Output is correct
8 Correct 2 ms 572 KB Output is correct
9 Execution timed out 1064 ms 572 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 572 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -