제출 #299015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
299015		Batyr	커다란 상품 (IOI17_prize)	C++17	90 / 100	113 ms	2816 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define pii pair<int,int>
 
const int maxn=2e5+5;
int dp[maxn][3],ans;
queue<pii>q;
 
int find_best(int n){
	memset(dp,-1,sizeof(dp));
	q.push({0,n-1});
	while(!q.empty()){
		int l=q.front().ff;
		int r=q.front().ss;
		q.pop();
		if(dp[l][0]==-1 and dp[l][1]==-1){
			vector<int> p=ask(l);
			dp[l][0]=p[0];
			dp[l][1]=p[1];
		}
		if(dp[l][0]+dp[l][1] == 0) return l;
		if(dp[r][0]==-1 and dp[r][1] == -1){
			vector<int> p=ask(r);
			dp[r][0]=p[0];
			dp[r][1]=p[1];
		}
		if(dp[r][0]+dp[r][1] == 0) return r;
		if(dp[l][0]+dp[l][1]==dp[r][0]+dp[r][1] and dp[r][0]-dp[l][0] == 0) continue;
		q.push({l,(l+r)/2});
		q.push({(l+r)/2+1,r});
	}
}

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

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

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