oj.uz

Submission #544910

# Submission time Handle Problem Language Result Execution time Memory
544910 2022-04-03T06:31:55 Z MilosMilutinovic Red-blue table (IZhO19_stones) C++14
100 / 100
 93 ms 3268 KB 
#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

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);
      |  ~~~~~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1284 KB Output is correct
2 Correct 82 ms 2508 KB Output is correct
3 Correct 73 ms 2604 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1380 KB Output is correct
2 Correct 68 ms 1980 KB Output is correct
3 Correct 63 ms 1692 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 5 ms 340 KB Output is correct
5 Correct 90 ms 1284 KB Output is correct
6 Correct 82 ms 2508 KB Output is correct
7 Correct 73 ms 2604 KB Output is correct
8 Correct 87 ms 1380 KB Output is correct
9 Correct 68 ms 1980 KB Output is correct
10 Correct 63 ms 1692 KB Output is correct
11 Correct 21 ms 524 KB Output is correct
12 Correct 69 ms 1888 KB Output is correct
13 Correct 73 ms 1668 KB Output is correct
14 Correct 53 ms 1280 KB Output is correct
15 Correct 93 ms 3268 KB Output is correct
16 Correct 68 ms 2500 KB Output is correct
17 Correct 28 ms 1276 KB Output is correct