Submission #104225

#	Time	Username	Problem	Language	Result	Execution time	Memory
104225		RockyB	The Big Prize (IOI17_prize)	C++17	100 / 100	77 ms	5500 KiB

prize

#include "prize.h"
#include "bits/stdc++.h"
using namespace std;
bool done[200001];
vector < int > mem[200001];
vector < int > myask(int idx){
	if(done[idx]){
		return mem[idx];
	}
	done[idx] = 1;
	return mem[idx] = ask(idx);
}
int solve(int rsmall , int ql , int qr , int mx){
	if(ql > qr){
		return -1;
	}
	int l = ql;
	int r = qr;
	while(l < r){
		int mid = l + r >> 1;
		vector < int > tmp = myask(mid);
		if(tmp[0] + tmp[1] == 0){
			return mid;
		}
		if(tmp[0] + tmp[1] == mx){
			if(rsmall - tmp[1]){
				r = mid - 1;
			}
			else{
				l = mid + 1;
			}
		}
		else{
			r = mid;
		}
	}
	while(l <= qr){
		vector < int > tmp = myask(l);
		if(tmp[0] + tmp[1] == 0){
			return l;
		}
		if(tmp[0] + tmp[1] == mx){
			break;
		}
		++l;
	}
	if(l == qr + 1){
		return -1;
	}
	if(mem[l][1] - mem[qr + 1][1]){
		return solve(myask(l)[1] , l + 1 , qr , mx);
	}
	return -1;
}
int find_best(int n){
	int mx = 0;
	memset(done , 0 , sizeof(done));
	int groups = 460;
	int small = n / 460;
	int large = small + 1;
	int cur = 0;
	vector < int > ids;
	ids.clear();
	for(int i = 0 ; i < groups ; ++i){
		vector < int > res = myask(cur);
		mx = max(mx , res[0] + res[1]);
		if(res[0] + res[1] == 0){
			return cur;
		}
		ids.push_back(cur);
		if(i < (n % 460)){
			cur += large;
		}
		else{
			cur += small;
		}
	}
	done[n] = 1;
	mem[n] = {mx , 0};
	ids.push_back(n);
	for(int i = 0 ; i + 1 < ids.size() ; ++i){
		int x = ids[i];
		int y = ids[i + 1];
		int res = -1;
		if(mem[x][0] + mem[x][1] == mx && mem[y][0] + mem[y][1] == mx){
			if(mem[x][1] - mem[y][1]){
				res = solve(mem[x][1] , x + 1 , y - 1 , mx);
			}
			else{
				res = -1;
			}
		}
		else if(mem[x][0] + mem[x][1] == mx && mem[y][0] + mem[y][1] < mx){
			while(y >= x){
				vector < int > tmp = myask(y);
				if(tmp[0] + tmp[1] == 0){
					return y;
				}
				if(tmp[0] + tmp[1] == mx){
					break;
				}
				--y;
			}
			if(y == x - 1){
				res = -1;
			}
			else{
				if(mem[x][1] - mem[y][1]){
					res = solve(mem[x][1] , x + 1 , y - 1 , mx);
				}
				else{
					res = -1;
				}			
			}
		}
		else{
			while(x <= y){
				vector < int > tmp = myask(x);
				if(tmp[0] + tmp[1] == 0){
					return x;
				}
				if(tmp[0] + tmp[1] == mx){
					break;
				}
				++x;
			}
			if(x == y + 1){
				res = -1;	
			}
			else{
				if(mem[y][0] + mem[y][1] == mx){
					if(mem[x][1] - mem[y][1]){
						res = solve(mem[x][1] , x + 1 , y - 1 , mx);
					}
					else{
						res = -1;
					}
				}
				else{
					while(y >= x){
						vector < int > tmp = myask(y);
						if(tmp[0] + tmp[1] == 0){
							return y;
						}
						if(tmp[0] + tmp[1] == mx){
							break;
						}
						--y;
					}
					if(y == x - 1){
						res = -1;
					}
					else{
						if(mem[x][1] - mem[y][1]){
							res = solve(mem[x][1] , x + 1 , y - 1 , mx);
						}
						else{
							res = -1;
						}			
					}
				}
			}
		}
		if(res != -1){
			return res;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int solve(int, int, int, int)':
prize.cpp:20:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:81:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i + 1 < ids.size() ; ++i){
                  ~~~~~~^~~~~~~~~~~~
prize.cpp:168:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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