제출 #953048

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953048		waldi	커다란 상품 (IOI17_prize)	C++17	97.42 / 100	30 ms	6732 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
using namespace std;

int find_best(int n){
	vector<vector<int>> tab(n);
	auto zapytaj = [&](int i){
		if(tab[i].empty()) tab[i] = ask(i);
		return tab[i];
	};
	
	if(n <= 5000){
		REP(i, n) if(zapytaj(i)[0]+zapytaj(i)[1] == 0) return i;
		return -69;
	}
	
	int maks = 0;
	REP(i, min(n, 500)){
		int t = zapytaj(i)[0] + zapytaj(i)[1];
		if(!t) return i;
		maks = max(maks, t);
	}
	
	int wynik = -1;
	function<void(int, int, int, int)> zwyciezaj = [&](int p, int k, int przed, int tutaj){
		//~ printf("%d %d  %d %d\n", p, k, przed, tutaj);
		if(wynik>=0 || p>k || !tutaj) return;
		int sr_org = (p+k)>>1;
		
		int sr = sr_org;
		vector<int> t = zapytaj(sr);
		while(1){
			if(t[0]+t[1] == 0) return void(wynik = sr);
			if(t[0]+t[1] == maks) break;
			--sr;
			if(sr < p) break;
			t = zapytaj(sr);
		}
		int lewo = sr>=p ? t[0]-przed : 0;
		
		int roz = sr_org-sr;
		zwyciezaj(p, sr-1, przed, lewo);
		zwyciezaj(sr_org+1, k, przed+lewo+roz, tutaj-lewo-roz);
	};
	zwyciezaj(0, n-1, 0, maks);
	return wynik;
}

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