Submission #432462

#	Time	Username	Problem	Language	Result	Execution time	Memory
432462		jeroenodb	The Big Prize (IOI17_prize)	C++14	100 / 100	61 ms	996 KiB

prize

#ifndef GRADER
#include "prize.h"
#endif
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;


int find_best(int n) {
	map<int,vi> qs;
	map<int,set<int>> ma;
	set<pi> intervals = {{0,n-1}};
	auto removeivs = [&](int l, int r) {
		intervals.erase(intervals.lower_bound(pi{l,-oo}), intervals.upper_bound(pi{r,-oo}));
	};
	while(!intervals.empty()) {
		auto iv = *intervals.begin();
		intervals.erase(intervals.begin());
		int mid = (iv.first+iv.second+1)/2;
		auto v = qs[mid] = ask(mid);
		int type = v[0]+v[1];
		if(type==0) return mid;
		auto [it,good] = ma[type].insert(mid);
		if(iv.first<=mid-1) intervals.insert(pi{iv.first,mid-1});
		if(mid+1<=iv.second) intervals.insert(pi{mid+1,iv.second});
		if(it==ma[type].begin() ) {
			if(v[0]==0) removeivs(0,mid);
		} else {
			auto vv = qs[*prev(it)];
			if(vv[0]==v[0]) removeivs(*prev(it),mid);
		}
		if(next(it)==ma[type].end()) {
			if(v[1]==0) removeivs(mid,n);
		} else {
			auto vv = qs[*(++it)];
			if(vv[1]==v[1]) removeivs(mid,*it);
		}
	}
	return -1;

}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |   auto [it,good] = ma[type].insert(mid);
      |        ^

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