oj.uz

Submission #790689

# Submission time Handle Problem Language Result Execution time Memory
790689 2023-07-23T06:12:32 Z PoonYaPat The Big Prize (IOI17_prize) C++14
0 / 100
 84 ms 5036 KB 
#include "prize.h"
#include <bits/stdc++.h>
using namespace std;

int mmax=0,st,n;
vector<int> val[200005];
vector<int> none;

void find_nxt() { //find the next non-lollipop
	int l=st+1,r=n-1;
	while (l<r) {
		int mid=(l+r)/2;
		val[mid]=ask(mid);
		if (val[mid][0]+val[mid][1]!=mmax) r=mid;
		else if (val[mid][0]!=val[st][0]) r=mid;
		else l=mid+1;
	}
	none.push_back(l);
	for (int i=l+1; i<n; ++i) {
		val[i]=ask(i);
		if (val[i][0]+val[i][1]!=mmax) none.push_back(i);
		else {
			st=i;
			find_nxt();
		}
	}
}

int find_best(int N) {
	n=N;
	for (int i=0; i<min(500,n); ++i) {
		val[i]=ask(i);
		mmax=max(mmax,val[i][0]+val[i][1]);
	}
	for (int i=0; i<min(500,n); ++i) {
		if (val[i][0]+val[i][1]==mmax) {
			st=i;
			find_nxt();
			break;
		} else none.push_back(i);
	}

	for (auto s : none) {
		val[s]=ask(s);
		if (val[s][0]+val[s][1]==0) return s;
	}
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 4988 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 5036 KB Incorrect
2 Halted 0 ms 0 KB -