Submission #838195

#	Time	Username	Problem	Language	Result	Execution time	Memory
838195		Ronin13	The Big Prize (IOI17_prize)	C++17	90 / 100	74 ms	1204 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
map <int, vector <int> > mp;
int find_best(int n) {
	int x = 472;
	int mx = -1e9, mni;
	for(int i = 0; i < min(x, n); i++){
		vector <int> v = ask(i);
		if(v[0] == 0 && v[1] == 0){
			return i;
		}
		if(v[0] + v[1] > mx)
			mx = v[0] + v[1], mni = i;
	}
	int cur = mni;
	int cnt = 0;
	vector <int> a = ask(mni);
	while(true){
		int l = cur, r = n;
		int x = r - l;
		x = sqrt(x);
		int mid = l + x - 1;
		if(mp[mid].empty()) mp[mid] = ask(mid);
		vector <int> o = mp[mid];
		if(a[1] - cnt == o[1]) l = mid;
		else r = mid;
		//vector <int> a = ask(mni);
		//if(a[1] - cnt == o[1]) break;
		while(l + 1 < r){
			int mid = (l + r) / 2;
			if(mp[mid].empty()) mp[mid] = ask(mid);
			vector <int> o = mp[mid];
			if(a[1] - cnt == o[1]) l = mid;
			else r = mid;
		}
		cur = r;
		if(r == n) break;
		o = mp[r];
		if(o[0] == 0 && o[1] == 0) return r;
		cnt++;
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:26:26: warning: 'mni' may be used uninitialized in this function [-Wmaybe-uninitialized]
   26 |  vector <int> a = ask(mni);
      |                          ^

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