Submission #1075948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075948		Abito	The Big Prize (IOI17_prize)	C++17	90 / 100	64 ms	2424 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+5;
int ans[N][2],S;
bool vis[N];
int32_t find_best(int32_t n) {
	int s=0,mx=0;
	for (int i=0;i<min(500,n);i++){
		vector<int32_t> v=ask(i);
		ans[i][0]=v[0];
		ans[i][1]=v[1];
		vis[i]=1;
		if (v[0]+v[1]==0) return i;
		if (v[0]+v[1]>mx){
			mx=v[0]+v[1];
			s=i;
		}
	}
	while (s<=n){
		int l=s,r=n,mid,idx;
		while (l<=r){
			mid=(l+r)/2;
			if (!vis[mid]){
				vector<int> v=ask(mid);
				ans[mid][0]=v[0];
				ans[mid][1]=v[1];
			}
			if (ans[mid][0]==ans[s][0] && ans[mid][1]==ans[s][1]){
				idx=mid;
				l=mid+1;
			}else r=mid-1;
		}
		if (idx==n) break;
		for (int i=idx+1;i<=n;i++){
			if (!vis[i]){
				vector<int> v=ask(i);
				ans[i][0]=v[0];
				ans[i][1]=v[1];
			}
			if (ans[i][0]+ans[i][1]==mx){
				s=i;
				break;
			}
			if (ans[i][0]+ans[i][1]==0) return i;
		}
	}
	return 0;
}

Compilation message (stderr)

prize.cpp: In function 'int32_t find_best(int32_t)':
prize.cpp:22:19: warning: 'idx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   22 |   int l=s,r=n,mid,idx;
      |                   ^~~

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