Submission #607686

#	Time	Username	Problem	Language	Result	Execution time	Memory
607686		Dan4Life	커다란 상품 (IOI17_prize)	C++17	20 / 100	78 ms	1304 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;
}
map<int, vector<int>> M;
 
vector<int> Ask(int x){
	if(M.count(x)) return M[x];
	return M[x] = ask(x);
}
int find_best(int n) {
	N=n; int l = 0, r = n-1, I = rand()%2;
	for(int i = 0; i < 500; i++){
		while(l+1<r){
			int mid = (l+r)/2;
			auto x = Ask(mid);
			if(x[0]+x[1]==0) return mid;
			if(I){
				if(x[0]!=query(0,mid-1)) r=mid-1;
	          	else l = mid+1;
			}
			else{
	          	if(x[1]!=query(mid+1,r)) l=mid+1;
	          	else  r = mid-1;
          	}
		}
		auto x = Ask(l), y = Ask(r);
		if(I){
	      	if(x[0]+x[1]==0) return l;
	      	if(y[0]+y[1]==0) return r;
	        if(y[0]!=query(0,r-1)) update(l,1);
			else update(r,1);
			l++;
		}
		else{
			if(x[0]+x[1]==0) return l;
	      	if(y[0]+y[1]==0) return r;
	        if(y[0]!=query(0,r-1)) update(l,1);
			else update(r,1);
			r--;
		}
		I = rand()%2;
	}
}

Compilation message (stderr)

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

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