제출 #790697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790697		PoonYaPat	The Big Prize (IOI17_prize)	C++14	90 / 100	83 ms	5520 KiB

prize

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

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

void find_nxt() { //find the next non-lollipop
	int l=st+1,r=n-1;
	if (none.size()==non_lol) return;
	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();
			break;
		}
	}
}

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]);
	}

	non_lol=n-mmax-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;
	}
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'void find_nxt()':
prize.cpp:11:17: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   11 |  if (none.size()==non_lol) return;
      |      ~~~~~~~~~~~^~~~~~~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:52:1: warning: control reaches end of non-void function [-Wreturn-type]
   52 | }
      | ^

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