제출 #260478

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

prize

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

#define vi vector<int>
#define pb push_back
#define F first
#define S second
#define pii pair<int,int>
#define all(v) v.begin(),v.end()

mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 

vector<pii> possible;
int mx;

void solve(int l,int r,int lcnt,int rcnt){
	// cout << l << " " << r << " " << lcnt << " " << rcnt << endl;
	if(l > r) return;
	if(lcnt+rcnt == mx) return;
	int mid = (l+r)/2;
	int m = mid;
	int bizz = 0;
	while(mid >= l){
		vi gg = ask(mid);
		if(gg[0]+gg[1] == mx){
			solve(l,mid-1,lcnt,gg[1]);
			solve(m+1,r,gg[0]+bizz,rcnt);
			return;
		}
		possible.pb({gg[0]+gg[1],mid});
		bizz++;
		mid--;
	}
	solve(m+1,r,lcnt+bizz,rcnt);
}

int find_best(int n) {
	vector<pii> r;
	for(int i = 0; i < 2000; i ++){
		int ind = RNG()%n;
		vi gg = ask(ind);
		r.pb({gg[0]+gg[1],ind});
	}
	sort(all(r));
	mx = r.back().F;
	solve(0,n-1,0,0);
	sort(all(possible));
	return possible[0].S;
}

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