Submission #544910

#TimeUsernameProblemLanguageResultExecution timeMemory
544910MilosMilutinovicRed-blue table (IZhO19_stones)C++14
100 / 100
93 ms3268 KiB
#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
template<typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}

int n,m,row[1000005],col[1000005],ord[1000005];

void solve(){
	scanf("%d%d",&n,&m);
	int bst=n,ty=0;
	vector<vector<char>> ans(n+1,vector<char>(m+1,'+'));
	vector<vector<char>> tmp(n+1,vector<char>(m+1,'+'));
	for(int i=1;i<=n;i++)row[i]=m;
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++)ord[i]=i;
		sort(ord+1,ord+n+1,[&](int x,int y){
			bool isx=(row[x]<=m-row[x]);
			bool isy=(row[y]<=m-row[y]);
			return isx>isy||(isx==isy&&row[x]>row[y]);
		});
		int tc=n/2+1;
		for(int i=1;i<=tc;i++)tmp[ord[i]][j]='-',row[ord[i]]--;
		int cur=j;
		for(int i=1;i<=n;i++)if(row[i]>m-row[i])cur++;
		if(cur>bst){
			for(int r=ty+1;r<=j;r++)for(int i=1;i<=n;i++)ans[i][r]=tmp[i][r];
			bst=cur,ty=j;
		}
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)tmp[i][j]='-';
	int tx=0;
	for(int i=1;i<=m;i++)col[i]=n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)ord[j]=j;
		sort(ord+1,ord+m+1,[&](int x,int y){
			bool isx=(col[x]<=n-col[x]);
			bool isy=(col[y]<=n-col[y]);
			return isx>isy||(isx==isy&&col[x]>col[y]);
		});
		int tc=m/2+1;
		for(int j=1;j<=tc;j++)tmp[i][ord[j]]='+',col[ord[j]]--;
		int cur=i;
		for(int j=1;j<=m;j++)if(col[j]>n-col[j])cur++;
		if(cur>bst){
			if(tx==0)for(int r=1;r<=n;r++)for(int c=1;c<=m;c++)ans[r][c]=tmp[r][c];
			for(int r=tx+1;r<=i;r++)for(int j=1;j<=m;j++)ans[r][j]=tmp[r][j];
			bst=cur,tx=i;
		}
	}
	printf("%d\n",bst);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)printf("%c",ans[i][j]);
		printf("\n");
	}
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}

Compilation message (stderr)

stones.cpp: In function 'void solve()':
stones.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
stones.cpp: In function 'int main()':
stones.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  scanf("%d",&T);
      |  ~~~~~^~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...