제출 #334724

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334724		LucaDantas	커다란 상품 (IOI17_prize)	C++17	20 / 100	85 ms	9112 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 = 2e6+10;

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

struct BIT
{
	int bit[maxn+1];

	void build() {
		for(int i = 1; i < maxn; i++)
			bit[i] = i&-i;
	}

	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 bs(int x) {
		int pos = 0;
		for(int l = 20; l >= 0; l--) {
			if(pos + (1 << l) >= maxn) continue;
			if(bit[pos + (1 << l)] < x)
				pos += (1 << l), x -= bit[pos];
		}
		return pos;
	}
} bit1, bit2;

int find_best(int n) {
	bit1.build();
	int base = 0;
	// int start = 0, base = 3;
	for(int i = 0; i < min(n, 475); i++) {
		vector<int> a = ask(i);
		base = max(base, a[0]+a[1]);
	}
	
	// printf("%d\n", base);

	// return 0;

	// printf("%d\n", bit1.bs(4));

	int qtd = 0;
	while(1) {
		++qtd;
		int l = 0, r = n-qtd;
		while(1) {
			int m = (l+r) >> 1;
			int pos = bit1.bs(m);
			bit1.upd(pos, -1);
			vector<int> a = ask(pos);
			// printf("%d %d %d\n", bit1.bs(m), a[0], a[1]);
			if(a == good) return pos;
			if(a[0]+a[1] == base) {
				if(a[0]-bit2.query(pos)) r = m-1;
				else l = m+1;
			} else {
				// puts("COMECOU");
				bit2.upd(pos, 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