Submission #953044

#	Time	Username	Problem	Language	Result	Execution time	Memory
953044		waldi	The Big Prize (IOI17_prize)	C++17	0 / 100	63 ms	6288 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){
		if(wynik>=0 || p>k || !tutaj) return;
		int sr_org = (p+k)>>1;
		
		int sr = sr_org, lewo = 0;
		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);
		}
		lewo = t[0]-przed;
		
		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: 0 / 20
• Subtask 2: 0 / 80