제출 #852612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
852612		midi	커다란 상품 (IOI17_prize)	C++17	92.69 / 100	36 ms	3672 KiB

prize

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

typedef long long ll;
#define vc vector
typedef vc<ll> vcll;
#define pr pair
typedef pr<ll,ll> prll;

#define f0r(i,a,n) for ((i)=(a); (i)<(n); (i)++)
#define f1r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>(a); (i)--)
#define r1f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define fi first
#define se second
#define pb push_back
#define mp make_pair

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

#define mxN 200'010ll
ll mxnon=500;

vc<prll> rember(mxN, {-1,-1});

ll n;
ll lols;
ll diamond;

/*
inline vc<int> ask(ll i)
{
	vc<int> res(2);
	printf("i=%lli : ", i);
	scanf("%i%i", &res[0], &res[1]);
	return res;
}
*/

inline prll asker(ll i)
{
	if (rember[i].fi!=-1) return rember[i];
	vc<int> res = ask(i);
	rember[i].fi=res[0];
	rember[i].se=res[1];
	return rember[i];
}

inline ll find_lols()
{
	ll i;
	ll s=-1;
	f0r(i,0,mxnon)
	{
		prll res = asker(i);
		if (res.fi+res.se==0)
		{
			diamond=i;
			return -1;
		}
		maxa(s, res.fi + res.se);
	}
	// printf("find_lols done\n");
	return s;
}

inline ll check_all(ll l, ll r)
{
	ll i;
	f0r(i,l,r+1)
	{
		prll res = asker(i);
		if (res.fi+res.se==0)
		{
			diamond=i;
			return 1;
		}
	}
	return 0;
}

ll find_diamond(ll l, ll r, prll left_res, prll right_res) // fi is left, se is right (obv.)
{
	/*
	printf("l: %lli, r: %lli\n", l, r);
	printf("left_res: {%lli %lli}\n", left_res.fi, left_res.se);
	printf("right_res: {%lli %lli}\n", right_res.fi, right_res.se);
	*/
	if (r-l<=3) return check_all(l,r);

	// pr<bool> dont_check = {0,0};

	ll m=(l+r)/2;
	ll l1, r1;
	// prll res=asker(m); // why the fuck did i write this
	prll res;
	ll i=m;
	while (i<r) // aaa
	{
		res = asker(i);
		l1=res.fi, r1=res.se;
		if (l1+r1==lols) break;
		if (l1+r1==0)
		{
			diamond=i;
			return 1;
		}
		i++;
	}
	if (i==r)
	{
		res = asker(m);
		right_res.fi = right_res.fi - (r+1 - m);
		right_res.se = right_res.se + (r+1 - m);

		return find_diamond(l, m-1, left_res, right_res);

		/*
		dont_check.se=1;
		i=m-1;
		while (i>l)
		{
			res = asker(i);
			l1=res.fi, r1=res.se;
			if (l1+r1==lols) break;
			if (l1+r1==0)
			{
				diamond=i;
				return 1;
			}
			i--;
		}
		if (i==l) return 0;
		*/
	}

	// ll ml1=l1 - (i-m); // eeeeeeeeeeeeeeeeeeeeeeeeeeeeee
	// ll left_real=l1-left_res.fi;

	/*
	if (left_real)
	{
		if (find_diamond()) return 1;
	}
	*/

	// right_check
	ll right_real=r1-right_res.se;
	// printf("r1: %lli, right_res.se: %lli\n", r1, right_res.se);
	if (right_real)
	{
		if (find_diamond(i+1, r, asker(i), right_res)) return 1;
	}

	// left_check
	right_res.fi = l1 - (i-m);
	ll left_real = right_res.fi - left_res.fi;
	if (left_real)
	{
		right_res.se = r1 + i-m; // bad
		if (i!=m) right_res.se--;
		if (find_diamond(l, m-1, left_res, right_res)) return 1;
	}

	return 0;
}

inline ll find_diamond()
{
	ll i, j;
	prll res1, res2;
	
	f0r(i,0,n)
	{
		// printf("checking i: %lli\n", i);
		res1=asker(i);
		if (res1.fi+res1.se==0) return i;
		if (res1.fi+res1.se==lols) break;
	}
	
	r1f(j,n-1,0)
	{
		// printf("checking j: %lli\n", j);
		res2=asker(j);
		if (res2.fi+res2.se==0) return j;
		if (res2.fi+res2.se==lols) break;
	}
	
	find_diamond(i+1, j-1, res1, res2);
	return diamond;
	
	// ll l=0, r=n-1;
}

int find_best(int N)
{
	n=N;
	if (n==1) return 0; // maybe unec.
	mina(mxnon, n);
	lols = find_lols();
	// lols=5;
	return find_diamond();
}

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

prize.cpp: In function 'll find_diamond(ll, ll, prll, prll)':
prize.cpp:153:2: warning: 'r1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  153 |  if (right_real)
      |  ^~
prize.cpp:159:20: warning: 'l1' may be used uninitialized in this function [-Wmaybe-uninitialized]
  159 |  right_res.fi = l1 - (i-m);
      |                 ~~~^~~~~~~

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