Submission #286431

#	Time	Username	Problem	Language	Result	Execution time	Memory
286431		egekabas	The Big Prize (IOI17_prize)	C++14	20 / 100	151 ms	6036 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
vector<int> dp[200009];
int curval = 0;
int N;
vector<int> q(int x){
	if(dp[x].size())
		return dp[x];
	return dp[x] = ask(x);
}
vector<int> used;
int mark[200009];
int find_best(int n) {
	N = n;
	for(int i = 0; i < 470 && i < n; ++i)
		curval = max(curval, q(i)[0]+q(i)[1]);
	while(1){
		int l = 0, r = n-1;
		int lval = 0, rval = 0;
		while(l < r){
			int mid = (l+r)/2;
			while(mark[mid] && mid > l)
				--mid;
			while(mid < r && mark[mid])
				++mid;
			vector<int> cur = q(mid);
			if(cur[0] + cur[1] != curval){
				l = r = mid;
				continue;
			}
			if(cur[0]-(lower_bound(all(used), mid)-used.begin()) > 0)
				r = mid-1;
			else
				l = mid+1;
		}
		if(q(l)[0]+q(l)[1] == 0)
			return l;
		else{
			used.pb(l);
			int idx = used.size()-1;
			while(idx > 0 && used[idx] > used[idx-1]){
				swap(used[idx], used[idx-1]);
				--idx;
			}
			mark[l] = 1;
		}
	}
}

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:32:7: warning: unused variable 'lval' [-Wunused-variable]
   32 |   int lval = 0, rval = 0;
      |       ^~~~
prize.cpp:32:17: warning: unused variable 'rval' [-Wunused-variable]
   32 |   int lval = 0, rval = 0;
      |                 ^~~~

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