Submission #1243909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243909		thelegendary08	The Big Prize (IOI17_prize)	C++17	90 / 100	22 ms	1976 KiB

prize

#include "prize.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define vvi vector<vi>
#define mp make_pair
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define dout(x) cout<<x<<' '<<#x<<endl;
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
using namespace std;
vb isbig, vis; vpii rets; int n; int shit = 0;
pii press(int x){
	if(vis[x])return rets[x];
	else{
		auto y = ask(x); vis[x] = 1;
		rets[x] = mp(y[0], y[1]);
		return mp(y[0], y[1]);
	}
}
int sum(pii x){
	return x.first + x.second;
}
const int sq = 450;
signed find_best(signed n) {
	::n=n;
	if(n <= 3000){
		f0r(i, n){
			auto x = ask(i);
			if(x[0] == 0 && x[1] == 0){
				return i;
			}
		}
	}
	else{
		int fi = 0;
		isbig.resize(n); vis.resize(n); rets.resize(n);
		f0r(i, sq){
			press(i);
			if(rets[i].first + rets[i].second == 0){
				return i;
			}
		}
		
		f0r(i, sq){
			if(rets[i].first + rets[i].second > shit){
				shit = rets[i].first + rets[i].second;
			}
		}
		int ptr = sq;
		while(1){
			while(sum(press(ptr)) < shit){
				if(sum(press(ptr)) == 0)return ptr;
				ptr++;
			}
			pii tar = press(ptr);
			int lo = ptr; int hi = n-1;
			while(lo < hi){
				int mid = lo + (hi - lo + 1) / 2;
				press(mid);
				if(sum(press(mid)) == 0)return mid;
				if(rets[mid].first == tar.first && rets[mid].second == tar.second){
					lo = mid;
				}
				else{
					hi = mid - 1;
				}
			}
			ptr = lo + 1;
		}
	}
	
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
   76 | }
      | ^

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