제출 #122663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
122663		SirCeness	커다란 상품 (IOI17_prize)	C++14	0 / 100	5 ms	2108 KiB

prize

#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair
#include "prize.h"
using namespace std;
typedef long long ll;

int arr[200005];
int n;
int tmp[200005];
int maxx;
// 22

vector<pair<int, pair<int, int> > > vec;

//vector<int> ask(int i){}

void f(int l, int r, int tane){
	if (tane <= 0) return;
	assert(l <= r);
	int m = (l+r)/2;
	vector<int> ans = ask(arr[r]);
	while (ans[0] + ans[1] != maxx){
		vec.pb(mp(arr[r], mp(ans[0], ans[1])));
		r--;
		ans = ask(arr[r]);
	}
	int msol = m-1;
	vector<int> ans2 = ask(m);
	while (ans[0] + ans[1] != maxx) {
		vec.pb(mp(arr[m], mp(ans2[0], ans2[1])));
		m++;
		ans2 = ask(arr[m]);
	}
	f(m+1, r-1, ans2[1] - ans[1]);
	f(l, msol, tane - ans2[1] + ans[1]);
}

int find_best(int size){
	n = size;
	for (int i = 0; i < size; i++) arr[i] = i;
	
	maxx = 0;
	for (int i = 0; i < min(10, n); i++){
		vector<int> ans = ask(i);
		maxx = max(ans[0] + ans[1], maxx);
	}
	
	int l = 0;
	int r = n-1;
	vector<int> ans1 = ask(l);
	vector<int> ans2 = ask(r);
	while (ans1[0] + ans1[1] != maxx){
		vec.pb(mp(l, mp(ans1[0], ans1[1])));
		l++;
		ans1 = ask(l);
	}
	while (ans2[0] + ans2[1] != maxx){
		vec.pb(mp(r, mp(ans2[0], ans2[1])));
		r--;
		ans2 = ask(r);
	}
	f(l+1, r-1, ans2[0] - ans1[0]);
	
	for (int i = 0; i < vec.size(); i++){
		if (vec[i].second.first + vec[i].second.second == 0) return vec[i].first;
	}
	
	assert(0);
}

컴파일 시 표준 에러 (stderr) 메시지

prize.cpp: In function 'int find_best(int)':
prize.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); i++){
                  ~~^~~~~~~~~~~~

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