Submission #934899

#	Time	Username	Problem	Language	Result	Execution time	Memory
934899		GrindMachine	The Big Prize (IOI17_prize)	C++17	97.29 / 100	29 ms	2264 KiB

prize

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
https://codeforces.com/blog/entry/53595?#comment-376650

f(i+1) > f(i)^2
#of non-lollipops = O(sqrt(n))

just check all non-lollipops for diamond
efficiently find all non-lollipops

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
const int B = 256;

#include "prize.h"

vector<pii> dp(N,{-1,-1});

pii ask2(int i){
	if(dp[i].ff != -1) return dp[i];
	vector<int> v = ask(i);
	return dp[i] = {v[0],v[1]};
}

int find_best(int n) {
	int mx = -1, pos = -1;

	rep(i,485){
		auto [cl,cr] = ask2(i);
		int cnt = cl+cr;
		if(cnt == 0){
			return i;
		}

		if(cnt >= mx){
			mx = cnt;
			pos = i;
		}
	}

	assert(pos != -1);

	deque<int> dq;
	for(int i = pos+B; i < n; i += B){
		dq.pb(i);
	}

	// find the closest non-lollipop with ind > i
	// given that the curr pos is a lollipop
	while(pos < n-1){
		while(!dq.empty() and dq.front() <= pos){
			dq.pop_front();
		}

		auto [fcl,fcr] = ask2(pos);
		int l = pos+1, r = n-1;

		if(!dq.empty()){
			l = dq.back()+1;
			rep(i,sz(dq)){
				auto [cl,cr] = ask2(dq[i]);
				int cnt = cl+cr;
				bool ok = false;
 
				// mid is not a lollipop
				if(cnt != mx){
					ok = true;
				}
				else{
					// mid is a lollipop
					if(cl > fcl){
						ok = true;
					}
				}
 
				if(ok){
					if(!i){
						l = pos+1;
					}
					else{
						l = dq[i-1]+1;
					}
 
					r = dq[i];
					break;
				}
			}	
		}

		int first = -1;

		while(l <= r){
			// is there a lollipop in range [pos,mid]?
			int mid = (l+r) >> 1;
			auto [cl,cr] = ask2(mid);
			int cnt = cl+cr;
			bool ok = false;

			// mid is not a lollipop
			if(cnt != mx){
				ok = true;
			}
			else{
				// mid is a lollipop
				if(cl > fcl){
					ok = true;
				}
			}

			if(ok){
				first = mid;
				r = mid-1;
			}
			else{
				l = mid+1;
			}
		}

		if(first == -1){
			break;
		}

		pos = -1;

		// find the closest pos >= first that is a lollipop
		for(int i = first; i < n; ++i){
			auto [cl,cr] = ask2(i);
			int cnt = cl+cr;
			
			if(cnt == 0){
				return i;
			}

			if(cnt == mx){
				pos = i;
				break;
			}
		}

		if(pos == -1) break;
	}

	// assert(0);
	return -1;
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:28:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define rep(i, n) for(int i = 0; i < n; ++i)
      |                                    ^
prize.cpp:114:4: note: in expansion of macro 'rep'
  114 |    rep(i,sz(dq)){
      |    ^~~

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