Submission #64622

# Submission time Handle Problem Language Result Execution time Memory
64622 2018-08-05T05:17:55 Z nvmdava The Big Prize (IOI17_prize) C++17
0 / 100
10 ms 5048 KB
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> ans[200001];
map<int, set<int> > v;
int s = -1;

void solve(int l, int r){
	if(l > r || s != -1){
		return;
	}
	int m = (l + r) >> 1;
	if(ans[m].size() == 0)ans[m] = ask(m);
	if(ans[m][0] + ans[m][1] == 0){
		s = m;
		return;
	}
		
	v[ans[m][0] + ans[m][1]].insert(m);
	auto it = v.find(ans[m][0] + ans[m][1]);
	auto loc = it -> second.find(m);
	bool in = 0;
	auto tmp = loc;
	while(tmp != it -> second.begin()){
		if(ans[m][0] != ans[*tmp][0]){
			in = 1;
			tmp++;
			solve(l, *tmp);
			break;
		}
		tmp--;	
	}
	if(in == 0){
		tmp = it->second.begin();
		solve(l, *tmp - 1);
	} else {
		in = 0;
	}
	tmp = loc;
	while(tmp != it -> second.end()){
		if(ans[m][0] != ans[*tmp][0]){
			in = 1;
			tmp--;
			solve(*tmp, r);
			break;
		}
		tmp++;
	}
	if(in == 0){
		tmp = it->second.end();
		tmp--;
		solve(*tmp + 1, r);
	}
}

int find_best(int n) {
	solve(0, n - 1);
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:59:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 4984 KB answer is not correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 5048 KB answer is not correct
2 Halted 0 ms 0 KB -