Submission #680890

#	Time	Username	Problem	Language	Result	Execution time	Memory
680890		vjudge1	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	13 ms	1440 KiB

prison

#include<vector>
#define pr pair<int,int> 
#define vi vector<int> 
using namespace std;
int n;vector<vi>ans;vector<pr>a[33];
inline vi make(const int&x){return vi(1,x);}
inline vi make(const int&x,const int&y)
	{vector<int>o;o.emplace_back(x);o.emplace_back(y);return o;}
inline bool ok(const int&i,const int&l,const int&r)
{
	for(int j=0;j<a[i].size();++j)
	{
		if(a[i][j].first<=l&&l<=a[i][j].second)return 0;
		if(a[i][j].first<=r&&r<=a[i][j].second)return 0;
		if(l<=a[i][j].first&&a[i][j].first<=r)return 0;
		if(l<=a[i][j].second&&a[i][j].second<=r)return 0;
	}
	return 1;
}
inline void work(const int&i,const int&l,const int&r,const vi&u,
	const vi&v,const vi&w)
{
	for(int j=0;j<u.size();++j)for(int k=u[j];k<=v[j];ans[i][k++]=w[j]);
	if(l>=r)return;
	int o=ans[i][0],mid=l+r>>1,j;
	ans[i][l]=-o-1;ans[i][r]=-(o^1)-1;
	if(r-l==1)return;//边界
	if(r-l==2)//边界
	{
		for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))
		{
			a[j].emplace_back(l,r);ans[i][mid]=j;
			work(j,l+1,r-1,make(l,r),make(l,r),make(-(o^1)-1,-o-1));
			return;
		}
		ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
		j=ans[i][mid]=ans.size()-1;a[j].emplace_back(l,r);
		work(j,l+1,r-1,make(l,r),make(l,r),make(-(o^1)-1,-o-1));
		return;
	}
	if(r-l>=6)//分三半
	{
		int m1=l+(r-l-1.)/3+0.5,m2=r-(r-l-1.)/3+0.5;
		for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//左
		{
			a[j].emplace_back(l,r);
			for(int k=l+1;k<=m1;ans[i][k++]=j);
			work(j,l+1,m1,make(l,m1+1),make(l,r),make(-(o^1)-1,-o-1));
			goto qaq;
		}
		ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
		j=ans.size()-1;a[j].emplace_back(l,r);
		for(int k=l+1;k<=m1;ans[i][k++]=j);
		work(j,l+1,m1,make(l,m1+1),make(l,r),make(-(o^1)-1,-o-1));
		qaq:;
		for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//中
		{
			a[j].emplace_back(l,r);
			for(int k=m1+1;k<m2;ans[i][k++]=j);
			work(j,m1+1,m2-1,make(l,m2),make(m1,r),make(-(o^1)-1,-o-1));
			goto quq;
		}
		ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
		j=ans.size()-1;a[j].emplace_back(l,r);
		for(int k=m1+1;k<m2;ans[i][k++]=j);
		work(j,m1+1,m2-1,make(l,m2),make(m1,r),make(-(o^1)-1,-o-1));
		quq:;
		for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//右
		{
			a[j].emplace_back(l,r);
			for(int k=m2;k<r;ans[i][k++]=j);
			work(j,m2,r-1,make(l,r),make(m2-1,r),make(-(o^1)-1,-o-1));
			return;
		}
		ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
		j=ans.size()-1;a[j].emplace_back(l,r);
		for(int k=m2;k<r;ans[i][k++]=j);
		work(j,m2,r-1,make(l,r),make(m2-1,r),make(-(o^1)-1,-o-1));
		return;
	}
	for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//左半边
	{
		a[j].emplace_back(l,r);
		for(int k=l+1;k<=mid;ans[i][k++]=j);
		work(j,l+1,mid,make(l,mid+1),make(l,r),make(-(o^1)-1,-o-1));
		goto qwq;
	}
	ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
	j=ans.size()-1;a[j].emplace_back(l,r);
	for(int k=l+1;k<=mid;ans[i][k++]=j);
	work(j,l+1,mid,make(l,mid+1),make(l,r),make(-(o^1)-1,-o-1));
	qwq:;
	for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//右半边
	{
		a[j].emplace_back(l,r);
		for(int k=mid+1;k<r;ans[i][k++]=j);
		work(j,mid+1,r-1,make(l,r),make(mid,r),make(-(o^1)-1,-o-1));
		return;
	}
	ans.emplace_back(vi(n+1));ans.back()[0]=o^1;
	j=ans.size()-1;a[j].emplace_back(l,r);
	for(int k=mid+1;k<r;ans[i][k++]=j);
	work(j,mid+1,r-1,make(l,r),make(mid,r),make(-(o^1)-1,-o-1));
}
vector<vi>devise_strategy(int N)
{
	n=N;ans.emplace_back(vi(n+1));ans[0][0]=0;
	work(0,1,n,vi(),vi(),vi());
	return ans;
}

Compilation message (stderr)

prison.cpp: In function 'bool ok(const int&, const int&, const int&)':
prison.cpp:11:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |  for(int j=0;j<a[i].size();++j)
      |              ~^~~~~~~~~~~~
prison.cpp: In function 'void work(const int&, const int&, const int&, const std::vector<int>&, const std::vector<int>&, const std::vector<int>&)':
prison.cpp:23:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |  for(int j=0;j<u.size();++j)for(int k=u[j];k<=v[j];ans[i][k++]=w[j]);
      |              ~^~~~~~~~~
prison.cpp:25:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |  int o=ans[i][0],mid=l+r>>1,j;
      |                      ~^~
prison.cpp:30:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))
      |           ~^~~~~~~~~~~
prison.cpp:44:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//左
      |           ~^~~~~~~~~~~
prison.cpp:56:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//中
      |           ~^~~~~~~~~~~
prison.cpp:68:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//右
      |           ~^~~~~~~~~~~
prison.cpp:81:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//左半边
      |          ~^~~~~~~~~~~
prison.cpp:93:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(j=1;j<ans.size();++j)if(ans[j][0]^o)if(ok(j,l,r))//右半边
      |          ~^~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 90 / 90