Submission #705759

#	Time	Username	Problem	Language	Result	Execution time	Memory
705759		Abrar_Al_Samit	The Big Prize (IOI17_prize)	C++17	20 / 100	70 ms	336 KiB

prize

#include<bits/stdc++.h>
#include "prize.h"
using namespace std;

int find_best(int n) {

	int sq = min(n, 400);
	int mx = -1, id;

	int cnt = 0;

	auto up = [&] () {
		++cnt;
		if(cnt>10000) assert(false);
	};
	vector<int>prv;
	for(int i=0; i<sq; ++i) {
		up();
		auto v = ask(i);
		if(v[0]+v[1]==0) {
			return i;
		}
		if(v[0]+v[1]>=mx) {
			mx = v[0] + v[1];
			id = i;
			prv = v;
		}
	}

	while(id<n-1) {
		int to = min(n-1, id+sq);
		up();
		auto cr = ask(to);
		if(cr[0]==prv[0] && cr[1]==prv[1]) {
			id = to;
			continue;
		}
		if(n-id-1<=5) {
			++id;
			while(id<n) {
				cr = ask(id);
				if(cr[0]+cr[1]==0) return id;
				++id;
			}
		} else {
			auto fif = ask(id+5);
			int posfif = id+5;
			if(fif[0]+fif[1]==0) return id+5;
			if(fif[0]!=prv[0] || fif[1]!=prv[1]) {
				++id;
				while(id<n) {
					up();
					cr = ask(id);
					if(cr[0]+cr[1]==0) {
						return id;
					}
					if(cr[0]+cr[1]==mx && id>posfif) {
						prv = cr;
						break;
					}
					++id;
				}
				continue;
			}
		}

		int l = 0, r = to-id;
		while(l<r) {
			int mid = (l+r+1)/2;
			up();
			cr = ask(id+mid);
			if(cr[0]==prv[0] && cr[1]==prv[1]) {
				l = mid;
			} else {
				r = mid-1;
			}
		
		}
		id += l+1;
		while(id<n) {
			up();
			cr = ask(id);
			if(cr[0]+cr[1]==0) {
				return id;
			}
			if(cr[0]+cr[1]==mx) {
				prv = cr;
				break;
			}
			++id;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:16:13: warning: control reaches end of non-void function [-Wreturn-type]
   16 |  vector<int>prv;
      |             ^~~
prize.cpp:31:23: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |   int to = min(n-1, id+sq);
      |                     ~~^~~

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