Submission #1325721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325721		thelegendary08	The Big Prize (IOI17_prize)	C++17	95.51 / 100	15 ms	2012 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 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, B = 512;
signed find_best(signed 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;
		int seen = 0; f0r(i,sq)if(sum(rets[i]) < shit)seen++; 
		
		while(1){
			while(sum(press(ptr)) < shit){
				if(sum(press(ptr)) == 0)return ptr;
				ptr++; seen++;
			}
			if(ptr + B + 1 < n){
				pii tmp = press(ptr + B); if(tmp.first + tmp.second == shit && tmp.first == seen){ptr += B + 1; continue;}
			}
			
			// int lo = ptr, hi = min(n,ptr + B); 
			// while(lo < hi){
				// int mid = lo + (hi - lo + 1) / 2; if(sum(press(mid)) == 0)return mid;
				// if(sum(rets[mid]) == shit && rets[mid].first == seen)lo=mid; else hi=mid-1;
			// }
			pii tar = press(ptr);
			int lo = ptr; int hi = min(n-1,ptr + B - 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:86:1: warning: control reaches end of non-void function [-Wreturn-type]
   86 | }
      | ^

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