Submission #283968

#	Time	Username	Problem	Language	Result	Execution time	Memory
283968		erd1	The Big Prize (IOI17_prize)	C++14	100 / 100	61 ms	2072 KiB

prize

#include "prize.h"

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
typedef pair<int, int> pii;
typedef long long lld;
typedef long double ld;

vector<pii> queries;
set<int> sums; // total 5

pii query(int x){
		if(queries[x].ff != -1)return queries[x];
		vector<int> res = ask(x);
		queries[x] = {res[0], res[1]};
		sums.insert(res[0] + res[1]);
		return queries[x];
}

int sum(pii a){ return a.ff + a.ss; }

void finds(int n, int k){
	int l = 0, r = n+1; int c = 0;
	while(true){
		int lmd = l+r>>1, rmd = lmd;
		while(rmd < n && next(sums.find(sum(query(rmd)))) != sums.end()) rmd++;
		while(lmd >= 0 && next(sums.find(sum(query(lmd)))) != sums.end()) lmd--;
		for(int i = lmd; i < rmd; i++)if(query(i).ff + query(i).ss == 0)throw i;
		if(rmd == n || lmd < 0)return;
		if(query(rmd).ff > k && query(lmd).ff <= k)return;
		(query(lmd).ff > k?r:l) = lmd;
		if(c++ > 100)return;
	}
}

int find_best(int n) {
queries.resize(n, {-1, -1});
	try{
		for(int i = 0; i < 6; i++)
			for(int j = 0; j < 2000; j++)finds(n, j);
	}catch(int e){
		return e;
	}
}

Compilation message (stderr)

prize.cpp: In function 'void finds(int, int)':
prize.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int lmd = l+r>>1, rmd = lmd;
      |             ~^~
prize.cpp: In function 'int find_best(int)':
prize.cpp:48:1: warning: control reaches end of non-void function [-Wreturn-type]
   48 | }
      | ^

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