Submission #868184

#	Time	Username	Problem	Language	Result	Execution time	Memory
868184		n1k	The Big Prize (IOI17_prize)	C++17	0 / 100	4 ms	436 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int LOG = 18, TAKE = 450;

int find_best(int n) {
	int mn = 1e9, id, cnt = 0;
	for(int id = 0; id < min(TAKE, n); id++){
		auto c = ask(id);
		int s = c[0] + c[1];
		if(s == 0){
			return id;
		}
		mn = min(mn, s);
	}
	while(id < n){
		// find next smallest num
		for(; true; id++){
			auto c = ask(id);
			int s = c[0] + c[1];
			cnt = c[0];
			if(s == 0){
				return id;
			}
			if(s == mn){
				break;
			}
		}
		// overjump all min
		for(int j = LOG; j >= 0; j--){
			int jump = 1<<j;
			if(id + jump > n){
				continue;
			}
			auto c = ask(id + jump);
			int s = c[0] + c[1];
			if(s == 0){
				return  id + jump;
			}
			if(s == mn && c[0] == cnt){
				id += jump;
			}
		}
		// go to the next which is not min
		id++;
	}
	
	assert(false);
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:20:3: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |   for(; true; id++){
      |   ^~~

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