Submission #1325717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1325717		thelegendary08	The Big Prize (IOI17_prize)	C++17	20 / 100	27 ms	1936 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 = 5187324822;
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 = 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:27:25: warning: overflow in conversion from 'long int' to 'int' changes value from '5187324822' to '892357526' [-Woverflow]
   27 | const int sq = 450, B = 5187324822;
      |                         ^~~~~~~~~~
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: 0 / 80