Submission #790647

#	Time	Username	Problem	Language	Result	Execution time	Memory
790647		Amylopectin	The Big Prize (IOI17_prize)	C++14	100 / 100	61 ms	24068 KiB

prize

#include "prize.h"
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 1e6 + 10;
vector<int> ret[mxn] = {};
int ans = -1,cal = -1,tot;
int fii(int cl,int cr,int lea,int ria)
{
	int i,j,mid = (cl+cr) / 2,lva,rva,cou = 0,cru;
	if(ret[mid].size() == 0)
	{
		ret[mid] = ask(mid);
	}
	lva = ret[mid][0];
	rva = ret[mid][1];
	cru = mid;
	if(lva + rva > tot)
	{
		tot = lva + rva;
		cal = 1;
		return 0;
	}
	if(lva + rva == 0)
	{
		ans = cru;
		return 0;
	}
	while(lva + rva < tot)
	{
		if(lva + rva == 0)
		{
			ans = cru;
			return 0;
		}
		cou ++;
		cru ++;
		if(cru > cr)
		{
			break;
		}
		if(ret[cru].size() == 0)
		{
			ret[cru] = ask(cru);
		}
		lva = ret[cru][0];
		rva = ret[cru][1];
		if(lva + rva > tot)
		{
			tot = lva + rva;
			cal = 1;
			return 0;
		}
	}
	if(cru <= cr)
	{
		lva -= cou;
		if(lva - lea > 0 && mid > cl)
		{
			fii(cl,mid-1,lea,rva + cou);
			if(ans != -1|| cal == 1)
			{
				return 0;
			}
		}
		if(rva - ria > 0 && cru < cr)
		{
			fii(cru+1,cr,lva + cou,ria);
			if(ans != -1|| cal == 1)
			{
				return 0;
			}
		}
	}
	else 
	{
		cru = mid-1;
		if(ret[cru].size() == 0)
		{
			ret[cru] = ask(cru);
		}
		lva = ret[cru][0];
		rva = ret[cru][1];
		if(lva + rva > tot)
		{
			tot = lva + rva;
			cal = 1;
			return 0;
		}
		if(lva + rva == 0)
		{
			ans = cru;
			return 0;
		}
		while(lva + rva < tot)
		{
			if(lva + rva == 0)
			{
				ans = cru;
				return 0;
			}
			cou ++;
			cru --;
			if(cru < cl)
			{
				break;
			}
			if(ret[cru].size() == 0)
			{
				ret[cru] = ask(cru);
			}
			lva = ret[cru][0];
			rva = ret[cru][1];
			if(lva + rva > tot)
			{
				tot = lva + rva;
				cal = 1;
				return 0;
			}
		}
		if(cru < cl)
		{
			return 0;
		}
		if(lva - lea > 0 && cru > cl)
		{
			fii(cl,cru-1,lea,rva);
			if(ans != -1 || cal == 1)
			{
				return 0;
			}
		}
	}
	return 0;
}
int find_best(int n) 
{
	int i,j,cn,cm,fn,fm,mid = (n-1)/2;
	tot = -1;
	ret[mid] = ask(mid);
	tot = ret[mid][0] + ret[mid][1];
	while(1)
	{
		cal = -1;
		ans = -1;
		fii(0,n-1,0,0);
		if(cal == -1)
		{
			break;
		}
	}
	// for(int i = 0; i < n; i++) 
	// {
	// 	std::vector<int> res = ask(i);
	// 	if(res[0] + res[1] == 0)
	// 		return i;
	// }
	return ans;
}

Compilation message (stderr)

prize.cpp: In function 'int fii(int, int, int, int)':
prize.cpp:10:6: warning: unused variable 'i' [-Wunused-variable]
   10 |  int i,j,mid = (cl+cr) / 2,lva,rva,cou = 0,cru;
      |      ^
prize.cpp:10:8: warning: unused variable 'j' [-Wunused-variable]
   10 |  int i,j,mid = (cl+cr) / 2,lva,rva,cou = 0,cru;
      |        ^
prize.cpp: In function 'int find_best(int)':
prize.cpp:138:6: warning: unused variable 'i' [-Wunused-variable]
  138 |  int i,j,cn,cm,fn,fm,mid = (n-1)/2;
      |      ^
prize.cpp:138:8: warning: unused variable 'j' [-Wunused-variable]
  138 |  int i,j,cn,cm,fn,fm,mid = (n-1)/2;
      |        ^
prize.cpp:138:10: warning: unused variable 'cn' [-Wunused-variable]
  138 |  int i,j,cn,cm,fn,fm,mid = (n-1)/2;
      |          ^~
prize.cpp:138:13: warning: unused variable 'cm' [-Wunused-variable]
  138 |  int i,j,cn,cm,fn,fm,mid = (n-1)/2;
      |             ^~
prize.cpp:138:16: warning: unused variable 'fn' [-Wunused-variable]
  138 |  int i,j,cn,cm,fn,fm,mid = (n-1)/2;
      |                ^~
prize.cpp:138:19: warning: unused variable 'fm' [-Wunused-variable]
  138 |  int i,j,cn,cm,fn,fm,mid = (n-1)/2;
      |                   ^~

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