제출 #596639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596639		farhan132	커다란 상품 (IOI17_prize)	C++17	100 / 100	53 ms	436 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll Q = 5e3;

int ans = 0;
int god_number = 0;

void find(ll l, ll r, ll L, ll M, ll R){
	if(M <= 0 || r < l) return;
	ll m = (l + r)/2;
	auto v = ask(m);
	if(v[0] + v[1] == god_number){
		find(l, m-1, L, v[0] - L, v[1]);
		find(m+1, r, v[0], v[1] - R, R);
		return;
	}
	if(v[0] + v[1] == 0){
		ans = m;
		return;
	}
	ll L1 = l, R1 = m-1; ll c = 1; M--;
	while(L1 <= R1 && M){
		v = ask(R1);
		if(v[0] + v[1] == 0){
			ans = R1; return;
		}
		if(v[0] + v[1] == god_number){
			if(L1 <= R1-1){
				find(L1, R1-1, L, v[0] - L, v[1]);
			}
			find(m+1, r, v[0] + c, v[1] - c - R, R);
			return;
		}
		M--;
		R1--;
		c++;
	}
	if(!M) return;
	find(m+1, r, L + c, M, R);
	return;
}
ll _try(ll n, ll c){
	return 0;
}

int find_best(int n) {
	if(n < Q){
		for(ll i = 0; i < n; i++){
			auto v = ask(i);
			if(v[0] + v[1] == 0) return i; 
		}
	}
	vector < ll > c(500, 0);
	ll fact = 475;
	for(int i = 0; i <= fact; i++){
		auto v = ask(i);
		if(v[0] + v[1] == 0) return i;
		c[i] = v[0] + v[1];
		if(c[i] != god_number){
			god_number = max(c[i], god_number);
			continue;
		}
		if(c[i] * c[i] > n){
			fact = i;
			break;
		}

	}
	ll L = 0;
	for(ll i = 0; i <= fact; i++){
		if(c[i] != god_number) L++;
	}
	find(fact + 1, n-1, L , god_number - L, 0);

	return ans;
}

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