제출 #607667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
607667		Dan4Life	The Big Prize (IOI17_prize)	C++17	0 / 100	1533 ms	312 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
using namespace std;
 
int fenwick[300000]{0}, N;
int sum(int x){
	int s = 0;
	for(; x>0; x-=(x&-x))
		s+=fenwick[x];
	return s;
}
 
int query(int a, int b){return sum(b)-sum(a-1);}
 
void update(int x, int v){
	for(; x <= N; x+=(x&-x))
		fenwick[x]+=v;
}
 
int find_best(int n) {
	N=n; int l = -1, r = n-1;
	for(int i = 0; i < 500; i++){
		l++, r = n-1;
		while(l<r){
			int mid = (l+r+1)/2;
			auto x = ask(mid);
			if(x[0]+x[1]==0) return mid;
			if(x[0]==query(1,mid-1)) l=mid+1;
			else r=mid-1;
		}
		update(l,1);
	}
}

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

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

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