#1131643 (C++14) No.3335 ReCT

提出ソース

結果

問題	No.3335 ReCT
コンテスト
ユーザー	kotatsugame
提出日時	2025-11-07 22:23:09
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	15 ms / 2,000 ms
コード長	5,813 bytes
コンパイル時間	1,654 ms
コンパイル使用メモリ	97,772 KB
実行使用メモリ	7,720 KB
最終ジャッジ日時	2025-11-07 22:23:17
合計ジャッジ時間	7,463 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 2
other	AC * 97

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function ‘std::pair<int, std::vector<std::vector<int> > > solveT(int, int)’:
main.cpp:168:21: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  168 |                 auto[nK,ret]=solveT(3,W);
      |                     ^

ソースコード

raw source code

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
vector<vector<int> >tr(const vector<vector<int> >&A)
{
	assert(!A.empty()&&!A[0].empty());
	int H=A.size(),W=A[0].size();
	vector<vector<int> >ret(W,vector<int>(H));
	for(int i=0;i<H;i++)for(int j=0;j<W;j++)ret[j][i]=A[i][j];
	return ret;
}
pair<int,vector<vector<int> > >solveC(int H,int W)
{
	if(H<3||W<3)return{-1,{}};
	if(H%2==0)
	{
		int K=0;
		vector<vector<int> >ret;
		if(H%4==0)
		{
			if(H>4)
			{
				auto p=solveC(H-4,W);
				K=p.first;
				ret=p.second;
			}
			assert(ret.size()==H-4);
			ret.push_back(vector<int>(W,K+1));//H-4
			ret.push_back(vector<int>(W,K+2));//H-3
			ret.push_back(vector<int>(W,K+1));//H-2
			ret.push_back(vector<int>(W,K+2));//H-1
			ret[H-3][0]=K+1;
			ret[H-2][W-1]=K+2;
			K+=2;
		}
		else
		{
			if(H>6)
			{
				auto p=solveC(H-6,W);
				K=p.first;
				ret=p.second;
			}
			assert(ret.size()==H-6);
			ret.push_back(vector<int>(W,K+1));//H-6
			ret.push_back(vector<int>(W,K+2));//H-5
			ret.push_back(vector<int>(W,K+1));//H-4
			ret.push_back(vector<int>(W,K+3));//H-3
			ret.push_back(vector<int>(W,K+2));//H-2
			ret.push_back(vector<int>(W,K+3));//H-1
			ret[H-5][0]=K+1;
			ret[H-2][0]=K+3;
			ret[H-3][W-1]=K+2;
			ret[H-4][W-1]=K+2;
			K+=3;
		}
		return{K,ret};
	}
	if(W%2==0)
	{
		auto p=solveC(W,H);
		p.second=tr(p.second);
		return p;
	}
	assert(H%2==1&&W%2==1);
	if(min(H,W)==3)return{-1,{}};
	auto p=solveC(H-2,W-1);
	int K=p.first;
	auto ret=p.second;
	for(int i=0;i<ret.size();i++)ret[i].push_back(K+1);
	ret.insert(ret.begin(),vector<int>(W,K+1));
	ret.push_back(vector<int>(W,K+1));
	K++;
	return{K,ret};
}
pair<int,vector<vector<int> > >solveT(int H,int W)
{
	if(H>W)
	{
		auto p=solveT(W,H);
		if(p.first>0)p.second=tr(p.second);
		return p;
	}
	assert(H<=W);
	if(H==2)return{-1,{}};
	else if(H==3)
	{
		if(W<6)return{-1,{}};
		else
		{
			int K=4;
			vector<vector<int> >ret;
			ret.push_back({1,2,2,2,2});
			ret.push_back({1,1,2,3,4});
			ret.push_back({1,3,3,3,3});
			for(int i=0;i<W-6;i++)
			{
				ret[0].push_back(2);
				ret[1].push_back(4);
				ret[2].push_back(3);
			}
			ret[0].push_back(4);
			ret[1].push_back(4);
			ret[2].push_back(4);
			return{K,ret};
		}
	}
	else if(H==4)
	{
		int K=4;
		vector<vector<int> >ret;
		ret.push_back({1,2});
		ret.push_back({1,1});
		ret.push_back({1,3});
		ret.push_back({3,3});
		for(int i=0;i<W-4;i++)
		{
			ret[0].push_back(2);
			ret[1].push_back(1);
			ret[2].push_back(4);
			ret[3].push_back(3);
		}
		ret[0].push_back(2);
		ret[1].push_back(2);
		ret[2].push_back(4);
		ret[3].push_back(3);
		ret[0].push_back(2);
		ret[1].push_back(4);
		ret[2].push_back(4);
		ret[3].push_back(4);
		return{K,ret};
	}
	else if(H==5)
	{
		int K=5;
		vector<vector<int> >ret;
		ret.push_back({1,1,1});
		ret.push_back({2,1,4});
		ret.push_back({2,2,2});
		ret.push_back({2,3,5});
		ret.push_back({3,3,3});
		for(int i=0;i<W-5;i++)
		{
			ret[0].push_back(1);
			ret[1].push_back(4);
			ret[2].push_back(2);
			ret[3].push_back(5);
			ret[4].push_back(3);
		}
		ret[0].push_back(1);
		ret[1].push_back(4);
		ret[2].push_back(5);
		ret[3].push_back(5);
		ret[4].push_back(3);
		ret[0].push_back(4);
		ret[1].push_back(4);
		ret[2].push_back(4);
		ret[3].push_back(5);
		ret[4].push_back(3);
		return{K,ret};
	}
	else
	{
		auto p=solveT(H-3,W);
		int K=p.first;
		auto[nK,ret]=solveT(3,W);
		for(int i=0;i<ret.size();i++)
		{
			for(int&v:ret[i])v+=K;
			p.second.push_back(ret[i]);
		}
		K+=nK;
		return{K,p.second};
	}
}
pair<int,vector<vector<int> > >solveCT(int H,int W)
{
	if(H>W)
	{
		auto p=solveCT(W,H);
		if(p.first>0)p.second=tr(p.second);
		return p;
	}
	if(H==2)return{-1,{}};
	else if(H==3)
	{
		int K=2;
		vector<vector<int> >ret;
		ret.push_back(vector<int>(W,1));
		ret.push_back(vector<int>(W,2));
		ret.push_back(vector<int>(W,1));
		ret[0][W-1]=2;
		ret[2][W-1]=2;
		ret[1][0]=1;
		return{K,ret};
	}
	else if(H==4)
	{
		int K=3;
		vector<vector<int> >ret;
		ret.push_back({1,1});
		ret.push_back({2,2});
		ret.push_back({2,3});
		ret.push_back({2,2});
		for(int i=0;i<W-4;i++)
		{
			ret[0].push_back(1);
			ret[1].push_back(2);
			ret[2].push_back(3);
			ret[3].push_back(2);
		}
		ret[0].push_back(1);
		ret[1].push_back(1);
		ret[2].push_back(3);
		ret[3].push_back(2);
		ret[0].push_back(1);
		ret[1].push_back(3);
		ret[2].push_back(3);
		ret[3].push_back(3);
		return{K,ret};
	}
	else
	{
		if(H==5&&W==5)
		{
			int K=4;
			vector<vector<int> >ret={
				{1,1,1,1,1},
				{2,1,3,3,3},
				{2,2,2,2,3},
				{2,4,3,3,3},
				{4,4,4,4,4}
			};
			return{K,ret};
		}
		else
		{
			auto p=solveT(H-1,W-2);
			assert(p.first>0);
			int K=p.first;
			auto ret=p.second;
			for(int i=0;i<ret.size();i++)
			{
				ret[i].insert(ret[i].begin(),K+1);
				ret[i].push_back(K+1);
			}
			ret.push_back(vector<int>(W,K+1));
			K++;
			return{K,ret};
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	/*
	for(int H=2;H<=7;H++)for(int W=2;W<=7;W++)
	{
		auto p=solveT(H,W);
		if(p.first==-1)cout<<"NA ("<<H<<", "<<W<<")"<<endl;
		else
		{
			cout<<"FOUND ("<<H<<", "<<W<<")"<<endl;
			cout<<p.first<<endl;
			for(int i=0;i<H;i++)for(int j=0;j<W;j++)cout<<p.second[i][j]<<(j+1==W?"\n":" ");
		}
	}
	return 0;
	*/
	int H,W;cin>>H>>W;
	{
		auto p=solveC(H,W);
		if(p.first==-1)cout<<"-1\n";
		else
		{
			cout<<p.first<<"\n";
			for(int i=0;i<H;i++)for(int j=0;j<W;j++)cout<<p.second[i][j]<<(j+1==W?"\n":" ");
		}
	}
	{
		auto p=solveT(H,W);
		if(p.first==-1)cout<<"-1\n";
		else
		{
			cout<<p.first<<"\n";
			for(int i=0;i<H;i++)for(int j=0;j<W;j++)cout<<p.second[i][j]<<(j+1==W?"\n":" ");
		}
	}
	{
		auto p=solveCT(H,W);
		if(p.first==-1)cout<<"-1\n";
		else
		{
			cout<<p.first<<"\n";
			for(int i=0;i<H;i++)for(int j=0;j<W;j++)cout<<p.second[i][j]<<(j+1==W?"\n":" ");
		}
	}
}

yukicoder

結果

コンパイルメッセージ

ソースコード