Submission #596086

#	Time	Username	Problem	Language	Result	Execution time	Memory
596086		franfill	The Big Prize (IOI17_prize)	C++17	100 / 100	136 ms	1516 KiB

prize

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

struct fenwick
{
	int n;
	vector < int > T;
	
	fenwick(int n_)
	{
		n = n_ + 1;
		T.resize(n);
	}

	void add(int i, int v)
	{
		for (int k = i+1; k < n; k+=k&-k) T[k] += v;
	}

	int query(int i)
	{
		int ans = 0;
		for (int k = i+1; k; k -= k&-k) ans += T[k];
		return ans;
	}
};

int find_best(int n) {
	map < int , map < int , int > > queried;

	queue < pair < int , int > > toq;
	toq.emplace(0, n);
	fenwick ignore(n);

	while(!toq.empty())
	{
		auto [l, r] = toq.front();		
		toq.pop();
		int m = (l+r)/2;
		cerr << m << " " << ignore.query(m) << "\n";
		if (l >= r) continue;
		if (ignore.query(m) > 0) continue;
		cerr << "OK\n";

		auto res = ask(m);
		int left = res[0], right = res[1];
		int key = left+right;
		if (key == 0)
			return m;
		
		auto &occ = queried[key];	

		{
			auto it = occ.upper_bound(m);
			if (it != occ.end() && it->second == left)
			{
				while(it != occ.end() && it->second == left) it++;
				it--;
				int x = m, y = it->first;
				ignore.add(y, -1);
				ignore.add(x, 1);
				cerr << "ehi" << x << " " << y << "\n";
			}
		}

		{
			auto it = occ.upper_bound(m);
			if (it != occ.begin())
			{
				it--;
				while(it->second == left && it != occ.begin()) it--;
				it++;
				if (it->second == left && it->first < m)
				{
					int x=it->first, y = m;
					ignore.add(y, -1);
					ignore.add(x, 1);
					cerr << "ehi" << x << " " << y << "\n";
				}
			}
		}

		toq.emplace(l, m);
		toq.emplace(m, r);
		
		occ[m] = left;
	}
	
	return 0;
}

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