Submission #293208

#	Time	Username	Problem	Language	Result	Execution time	Memory
293208		luciocf	커다란 상품 (IOI17_prize)	C++14	20 / 100	8 ms	512 KiB

prize

#include <bits/stdc++.h>
#include "prize.h"
 
#define ff first
#define ss second
 
using namespace std;
 
typedef pair<int, int> pii;
 
const int maxn = 2e5+10;
 
int qtd[10];
int tot[10];
 
pii get(int i)
{
	vector<int> v = ask(i);
 
	return {v[0], v[1]};
}
 
int find_best(int n)
{
	int ind = 0;
	for (int i = 0; i < min(n, 500); i++)
	{
		pii v = get(i);
 
		if (v.ff+v.ss == 0) return i;
 
		if (v.ff+v.ss > qtd[1])
			qtd[1] = v.ff+v.ss, ind = i;
	}

	tot[1] = n-qtd[1];

	int ini = 0, fim = n-1, ans;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		pii v = get(mid);

		if (v.ff+v.ss < qtd[1])
		{
			ans = mid;
			qtd[2] = v.ff+v.ss;
			break;
		}

		if (v.ff) fim = mid-1;
		else ini = mid+1;
	}

	tot[2] = n-qtd[2]-tot[1];
	if (tot[2] == 1) return ans;

	ini = 0, fim = n-1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		pii v = get(mid);

		if (v.ff+v.ss < qtd[1] && v.ff+v.ss < qtd[2])
		{
			ans = mid;
			qtd[3] = v.ff+v.ss;
			break;
		}

		if (v.ff+v.ss == qtd[1])
		{
			if (v.ff-tot[2]) fim = mid-1;
			else ini = mid+1;
		}
		else
		{
			if (v.ff) fim = mid-1;
			else ini = mid+1;
		}
	}

	tot[3] = n-qtd[3]-tot[2]-tot[1];
	if (tot[3] == 1) return ans;

	ini = 0, fim = n-1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		pii v = get(mid);

		if (v.ff+v.ss < qtd[1] && v.ff+v.ss < qtd[2] && v.ff+v.ss < qtd[3])
		{
			ans = mid;
			qtd[4] = v.ff+v.ss;
			break;
		}

		if (v.ff+v.ss == qtd[1])
		{
			if (v.ff-tot[2]-tot[3]) fim = mid-1;
			else ini = mid+1;
		}
		else if (v.ff+v.ss == qtd[2])
		{
			if (v.ff-tot[3]) fim = mid-1;
			else ini = mid+1;
		}
		else
		{
			if (v.ff) fim = mid-1;
			else ini = mid+1;
		}
	}

	tot[4] = n-qtd[4]-tot[3]-tot[2]-tot[1];
	if (tot[4] == 1) return ans;

	ini = 0, fim = n-1;

	while (ini <= fim)
	{
		int mid = (ini+fim)>>1;

		pii v = get(mid);

		if (v.ff+v.ss < qtd[1] && v.ff+v.ss < qtd[2] && v.ff+v.ss < qtd[3] && v.ff+v.ss < qtd[4]) return mid;

		if (v.ff+v.ss == qtd[1])
		{
			if (v.ff-tot[2]-tot[3]-tot[4]) fim = mid-1;
			else ini = mid+1;
		}
		else if (v.ff+v.ss == qtd[2])
		{
			if (v.ff-tot[3]-tot[4]) fim = mid-1;
			else ini = mid+1;
		}
		else if (v.ff+v.ss == qtd[3])
		{
			if (v.ff-tot[4]) fim = mid-1;
			else ini = mid+1;
		}
		else
		{
			if (v.ff) fim = mid-1;
			else ini = mid+1;
		}
	}
}	

Compilation message (stderr)

prize.cpp: In function 'int find_best(int)':
prize.cpp:25:6: warning: variable 'ind' set but not used [-Wunused-but-set-variable]
   25 |  int ind = 0;
      |      ^~~
prize.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
  156 | }
      | ^
prize.cpp:38:26: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   38 |  int ini = 0, fim = n-1, ans;
      |                          ^~~

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