Submission #128314

#	Time	Username	Problem	Language	Result	Execution time	Memory
128314		mohammedehab2002	Minerals (JOI19_minerals)	C++14	100 / 100	151 ms	4004 KiB

minerals

#include "minerals.h"
#include <vector>
using namespace std;
int cur=0;
pair<int,int> dp[43005][2];
vector<int> v1,v2;
bool query(int x)
{
	int tmp=Query(x);
	if (cur==tmp)
	return 1;
	cur=tmp;
	return 0;
}
void solve(vector<int> a,vector<int> b,bool added)
{
	if (a.empty())
	return;
	if (a.size()==1)
	{
		Answer(a[0],b[0]);
		return;
	}
	int mid=dp[a.size()][added].second;
	if (a.size()>6000)
	{
		mid=(15*a.size()+4)/24;
		if (!added)
		mid=(9*a.size()+4)/24;
	}
	vector<int> aa[2],bb[2];
	for (int i=0;i<a.size();i++)
	{
		if (i<mid)
		{
			aa[0].push_back(a[i]);
			if (!added)
			query(a[i]);
		}
		else
		{
			aa[1].push_back(a[i]);
			if (added)
			query(a[i]);
		}
	}
	for (int i=0;i<b.size()-1;i++)
	{
		if (query(b[i]))
		bb[0].push_back(b[i]);
		else
		bb[1].push_back(b[i]);
	}
	if (aa[0].size()==bb[0].size())
	bb[1].push_back(b.back());
	else
	bb[0].push_back(b.back());
	solve(aa[0],bb[0],1);
	solve(aa[1],bb[1],0);
}
void Solve(int n)
{
	for (int i=1;i<=2*n;i++)
	{
		if (query(i))
		v2.push_back(i);
		else
		v1.push_back(i);	
	}
	for (int i=2;i<=6000;i++)
	{
		dp[i][0]={1e9,-1};
		dp[i][1]={1e9,-1};
		for (int j=1;j<=i-1;j++)
		{
			dp[i][0]=min(dp[i][0],{dp[j][1].first+dp[i-j][0].first+j+i-1,j});
			dp[i][1]=min(dp[i][1],{dp[j][1].first+dp[i-j][0].first+i-j+i-1,j});
		}
	}
	solve(v1,v2,1);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:32:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<a.size();i++)
               ~^~~~~~~~~
minerals.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<b.size()-1;i++)
               ~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10