Submission #900080

#	Time	Username	Problem	Language	Result	Execution time	Memory
900080		sysia	The Big Prize (IOI17_prize)	C++17	97.57 / 100	29 ms	684 KiB

prize

//Sylwia Sapkowska
#include <bits/stdc++.h>
#include "prize.h"
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
 
void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
typedef pair<int, int> T;
typedef array<int, 2> F;

int find_best(int n) {
	//juz nie trzeba szukac lizakow
	int ans = -1;
	function<void(int, int, F, F)>rec = [&](int l, int r, F L, F R){ 
		//szukamy odp na przedziale [l, r] i wyniki dla elementu pierwszego na lewo od l sa opisane jako para L 
		if (l > r) return;
		int m = (l+r)/2;
		auto x = ask(m);
		F a = {x[0], x[1]};
		if (a[0]+a[1] == 0) {
			ans = m;
			return;
		}
		if (a[0] && a != L) rec(l, m-1, L, a);
		if (ans == -1 && a[1] && a != R) rec(m+1, r, a, R);
		//popatrzmy na przedzial [l, m-1]
		//wiemy ze na lewo od m jest a[m][0] elementow
		//zeby oplacalo sie wywolac, musi byc ich dodatnia ilosc
		//L[0] to ilosc elementow na lewo od l-1
		//oczywiscie zachodzi a[m][0] >= L[0]
		//jesli a[m][0] > L[0], to warto wywolac sie na przedziale [l, m-1], bo moze byc jakis nowy element nienajgorszy na nim
		//jesli a[m][0] = L[0], to znaczy w szczegolnosci, ze te dwa elementy sa tego samego typu
		//(to wynika z faktu, ze ilosc elementow rosnie kwadratowo, i suma mniejszych jest mniejsza niz wartosc ilosci gorszego typu)
		//wiec skoro sa tego samego typu, i pomiedzy nie ma nic lepszego, to nie trzeba sie tam wywolywac
	};
	rec(0, n-1, {-1, -1}, {-1, -1});
	return ans;
}

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