Submission #161620

#	Time	Username	Problem	Language	Result	Execution time	Memory
161620		MvC	Red-blue table (IZhO19_stones)	C++11	100 / 100	113 ms	6516 KiB

stones

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e3+50;
const int mod=1e9+7;
int ts,i,j,t,cic[nmax],nr[nmax],tr,cur,rs,n,m,rs1;
vector<int>vc[nmax];
char c[nmax][nmax],ma[nmax][nmax],mb[nmax][nmax];
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>ts;
	while(ts--)
	{
		cin>>n>>m;
		rs=max(n,m);
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)c[i][j]='-';
		for(i=1;i<=m;i++)nr[i]=cic[i]=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<=n;j++)vc[j].clear();
			for(j=1;j<=m;j++)
			{
				if(nr[j]>n-n/2-1)cic[j]=1;
				if(!cic[j])vc[nr[j]].pb(j);
			}
			tr=m/2+1;
			for(j=1;j<=m;j++)
			{
				if(!tr)break;
				if(cic[j])
				{
					nr[j]++;
					tr--;
					c[i][j]='+';
				}
			}
			for(j=0;j<=n;j++)
			{
				if(!tr)break;
				for(t=0;t<(int)vc[j].size();t++)
				{
					if(!tr)break;
					c[i][vc[j][t]]='+';
					nr[vc[j][t]]++;
					tr--;
				}
			}
			cur=0;
			for(j=1;j<=m;j++)if(nr[j]<=n-n/2-1)cur++;
			rs=max(rs,cur+i);
		}
		if(rs==n)for(i=1;i<=n;i++)for(j=1;j<=m;j++)c[i][j]='+';
		if(rs==m)for(i=1;i<=n;i++)for(j=1;j<=m;j++)c[i][j]='-';
		if(rs==max(n,m))
		{
			cout<<rs<<'\n';
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=m;j++)cout<<c[i][j];
				cout<<'\n';
			}
			continue;
		}
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)c[i][j]='-';
		for(i=1;i<=m;i++)nr[i]=cic[i]=0;
		for(i=1;i<=n;i++)
		{
			for(j=0;j<=n;j++)vc[j].clear();
			for(j=1;j<=m;j++)
			{
				if(nr[j]>n-n/2-1)cic[j]=1;
				if(!cic[j])vc[nr[j]].pb(j);
			}
			tr=m/2+1;
			for(j=1;j<=m;j++)
			{
				if(!tr)break;
				if(cic[j])
				{
					nr[j]++;
					tr--;
					c[i][j]='+';
				}
			}
			for(j=0;j<=n;j++)
			{
				if(!tr)break;
				for(t=0;t<(int)vc[j].size();t++)
				{
					if(!tr)break;
					c[i][vc[j][t]]='+';
					nr[vc[j][t]]++;
					tr--;
				}
			}
			cur=0;
			for(j=1;j<=m;j++)if(nr[j]<=n-n/2-1)cur++;
			if(cur+i==rs)
			{
				for(i=1;i<=n;i++)for(j=1;j<=m;j++)ma[i][j]=c[i][j];
				break;
			}
		}
		rs1=max(n,m);
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)c[i][j]='+';
		for(i=1;i<=n;i++)nr[i]=cic[i]=0;
		for(i=1;i<=m;i++)
		{
			for(j=0;j<=m;j++)vc[j].clear();
			for(j=1;j<=n;j++)
			{
				if(nr[j]>m-m/2-1)cic[j]=1;
				if(!cic[j])vc[nr[j]].pb(j);
			}
			tr=n/2+1;
			for(j=1;j<=n;j++)
			{
				if(!tr)break;
				if(cic[j])
				{
					nr[j]++;
					tr--;
					c[j][i]='-';
				}
			}
			for(j=0;j<=m;j++)
			{
				if(!tr)break;
				for(t=0;t<(int)vc[j].size();t++)
				{
					if(!tr)break;
					c[vc[j][t]][i]='-';
					nr[vc[j][t]]++;
					tr--;
				}
			}
			cur=0;
			for(j=1;j<=n;j++)if(nr[j]<=m-m/2-1)cur++;
			rs1=max(rs1,cur+i);
		}
		for(i=1;i<=n;i++)for(j=1;j<=m;j++)c[i][j]='+';
		for(i=1;i<=n;i++)nr[i]=cic[i]=0;
		for(i=1;i<=m;i++)
		{
			for(j=0;j<=m;j++)vc[j].clear();
			for(j=1;j<=n;j++)
			{
				if(nr[j]>m-m/2-1)cic[j]=1;
				if(!cic[j])vc[nr[j]].pb(j);
			}
			tr=n/2+1;
			for(j=1;j<=n;j++)
			{
				if(!tr)break;
				if(cic[j])
				{
					nr[j]++;
					tr--;
					c[j][i]='-';
				}
			}
			for(j=0;j<=m;j++)
			{
				if(!tr)break;
				for(t=0;t<(int)vc[j].size();t++)
				{
					if(!tr)break;
					c[vc[j][t]][i]='-';
					nr[vc[j][t]]++;
					tr--;
				}
			}
			cur=0;
			for(j=1;j<=n;j++)if(nr[j]<=m-m/2-1)cur++;
			if(cur+i==rs1)
			{
				for(i=1;i<=n;i++)for(j=1;j<=m;j++)mb[i][j]=c[i][j];
				break;
			}
		}
		if(rs>rs1)
		{
			cout<<rs<<'\n';
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=m;j++)cout<<ma[i][j];
				cout<<'\n';
			}
		}
		else
		{
			cout<<rs1<<'\n';
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=m;j++)cout<<mb[i][j];
				cout<<'\n';
			}
		}
	}
	return 0;
}

Compilation message (stderr)

stones.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
stones.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

• Subtask 1: 17 / 17
• Subtask 2: 10 / 10
• Subtask 3: 16 / 16
• Subtask 4: 11 / 11
• Subtask 5: 15 / 15
• Subtask 6: 31 / 31