Submission #334675

#	Time	Username	Problem	Language	Result	Execution time	Memory
334675		LucaDantas	The Big Prize (IOI17_prize)	C++17	20 / 100	88 ms	620 KiB

prize

#include<bits/stdc++.h>
using namespace std;
#include "prize.h"

// std::vector<int> res = ask(i);

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count() ^ (long long) (make_unique<char>().get()));

template<typename T> T rnd(T v) {
  T k = (T) rng();
  return (T) (((k % v) + v) % v);
}

constexpr int maxn = 2e5+10;

const vector<int> good = {0, 0};

int bit[maxn];

void upd(int x, int v) {
	for(x++; x < maxn; x += x&-x)
		bit[x] += v;
}

int query(int x) {
	int ans = 0;
	for(x++; x > 0; x -= x&-x)
		ans += bit[x];
	return ans;
}

int find_best(int n) {
	int start = 0, base = 0;
	// int start = 0, base = 3;
	for(int i = 0; i < 10; i++) {
		vector<int> a = ask(rnd(n));
		base = max(base, a[0]+a[1]);
	}
	while(1) {
		int l = start, r = n-1;
		while(1) {
			int m = (l+r) >> 1;
			vector<int> a = ask(m);
			if(a == good) return m;
			if(a[0]+a[1] == base) {
				if(a[0]-query(m)) r = m-1;
				else l = m+1;
			} else {
				// puts("COMECOU");
				upd(m, 1);
				int p = m-1;
				while(p >= 0) {
					vector<int> a = ask(p);
					if(a[0]+a[1] == base) {
						if(!(a[0]-query(p)))
							start = m+1;
						break;
					}
					if(a == good) return p;
					upd(p, 1);
					--p;
				};
				// puts("TERMINOU");
				// printf("start %d\n", start);
				break;
			}
		}
	}
}

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