Submission #286396

#	Time	Username	Problem	Language	Result	Execution time	Memory
286396		egekabas	The Big Prize (IOI17_prize)	C++14	20 / 100	3031 ms	1920 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;
pii dp[200009];
int curval = 0;
int N;
pii q(int x){
	if(x < 0)
		return {0, curval};
	if(x >= N)
		return {curval, 0};
	if(dp[x].ff != -1)
		return dp[x];
	vector<int> v = ask(x);
	return dp[x] = {v[0], v[1]};
}
int bit[200009];
void upd(int idx, int val){
	for(++idx; idx <= 200000; idx += idx&(-idx))
		bit[idx] += val;
}
int get(int idx){
	int ret = 0;
	for(++idx; idx > 0; idx -= idx&(-idx));
		ret += bit[idx];
	return ret;
}
int get(int l, int r){
	return get(r)-get(l-1);
}

int find_best(int n) {
	N = n;
	for(int i = 0; i < n; ++i)
		dp[i] = {-1, -1};
	for(int i = 0; i < 555 && i < n; ++i)
		curval = max(curval, q(i).ff+q(i).ss);
	while(1){
		int l = 0, r = n-1;
		while(l < r){
			while(get(l, l) == -1) ++l;
			while(get(r, r) == -1) --r;
			if(l >= r) break;
			int mid = (l+r)/2;
			for(int i = 0; (mid-i) >= l || (mid+i) <= r; ++i){
				if((mid-i) >= l){
					int idx = mid-i;
					q(idx);
					if(dp[idx].ff+dp[idx].ss == 0)
						return idx;
					if(dp[idx].ff+dp[idx].ss == curval){
						if(q(idx).ff-q(l-1).ff-get(l, idx) > 0){
							r = idx-1;
							break;
						}
					}
					else{
						if(get(idx, idx) != -1)
							upd(idx, -1);
					}
				}
				if((mid+i) <= r){
					int idx = mid+i;
					q(idx);
					if(dp[idx].ff+dp[idx].ss == 0)
						return idx;
					if(dp[idx].ff+dp[idx].ss == curval){
						if(q(idx).ss-q(r+1).ss-get(idx, r) > 0){
							l = idx+1;
							break;
						}
					}
					else{
						if(get(idx, idx) != -1)
							upd(idx, -1);
					}
				}
			}
		}
		if(q(l).ff+q(l).ss == 0)
			return l;
		else
			upd(l, -1);
	}
}

Compilation message (stderr)

prize.cpp: In function 'int get(int)':
prize.cpp:36:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   36 |  for(++idx; idx > 0; idx -= idx&(-idx));
      |  ^~~
prize.cpp:37:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   37 |   ret += bit[idx];
      |   ^~~

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