Submission #790774

#	Time	Username	Problem	Language	Result	Execution time	Memory
790774		NothingXD	커다란 상품 (IOI17_prize)	C++17	0 / 100	3062 ms	1840 KiB

prize

#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cerr << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 2e5 + 10;
const int sq = 500;
int n, a[maxn][2];

void askq(int x){
	if (a[x][0] != -1) return;
	vector<int> res = ask(x);
	a[x][0] = res[0];
	a[x][1] = res[1];
}

bool ans(int x){
	return (a[x][0] == 0 && a[x][1] == 0);
}

int find_best(int _n) {
	memset(a, -1, sizeof a);
	for (int i = 0; i < sq; i++){
		askq(i);
		if (ans(i)) return i;
	}
	int pre = sq-1;
	for (int i = sq-1; ~i; i--){
		if (a[i][0] + a[i][1] > a[pre][0] + a[pre][1]) pre = i;
	}
	while(true){
		int l = pre, r = n+1;
		while(l + 1 < r){
			int mid = (l + r) >> 1;
			int x = mid;
			bool flg = false;
			while(x != l){
				askq(x);
				if (ans(x)) return x;
				if (a[x][0] + a[x][1] != a[pre][0] + a[pre][1]){
					x--; continue;
				}
				if (a[x][0] - a[pre][0] > 0){
					flg = true;
				}
				break;
			}
			if (flg) r = x;
			else l = mid;
		}
		while(a[l][0] + a[l][1] != a[pre][0] + a[pre][1]){
			l++;
			askq(l);
			if (ans(l)) return l;
		}
		pre = l;
	}
}

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