#include<iostream>
#include<cstring>
#include<random>
#include<vector>
#include<algorithm>
using namespace std;
int a[10][10];
int cnt = 0;
int answer = 0;
/*
int evaluate()
{
int A = 0, B = 0;
for(int i = 0;i<n;i++)
{
int cnt[2] = {0, 0};
for(int j = 0;j<m;j++)
{
cnt[ a[i][j] ]++;
}
if(cnt[0]>cnt[1]) A++;
}
for(int j = 0;j<m;j++)
{
int cnt[2] = {0, 0};
for(int i = 0;i<n;i++)
{
cnt[ a[i][j] ]++;
}
if(cnt[0]<cnt[1]) B++;
}
return A + B;
}
void gen(int i, int j)
{
if(i==n)
{
answer = max(answer, evaluate());
return;
}
if(j==m)
{
gen(i+1, 0);
return;
}
a[i][j] = 0;
gen(i, j+1);
a[i][j] = 1;
gen(i, j+1);
}
*/
vector <int> ruined;
vector <int> toAdd[1005];
vector <int> cnt2Columns[1005];
bool bestMode;
int bestN, bestM, bestRows;
bool matrix[1005][1005];
int myCalc(int n, int m, bool mode)
{
ruined.clear();
for(int i = 0;i<=max(n, m);i++)
{
toAdd[i].clear();
cnt2Columns[i].clear();
}
for(int j = 0;j<m;j++)
{
cnt2Columns[0].push_back(j);
}
//cout << answer << " vs " << m << '\n';
if(answer < m)
{
answer = m;
bestN = n;
bestM = m;
bestRows = -1;
bestMode = mode;
}
for(int row = 0;row<n;row++)
{
/*
cout << "ruined:";
for(int x: ruined) cout << " " << x;
cout << '\n';
for(int cnt = 0;cnt<=(n-1)/2;cnt++)
{
cout << cnt << ":";
for(int x: cnt2Columns[cnt]) cout << " " << x;
cout << '\n';
}
cout << " ---- --- --- " << '\n';
*/
int toFill = m/2 + 1;
for(int i = 0;i<ruined.size();i++)
{
toFill--;
if(toFill==0) break;
}
for(int cnt = 0;cnt<=(n-1)/2;cnt++)
{
while(toFill>0 && cnt2Columns[cnt].empty()==false)
{
toAdd[cnt+1].push_back(cnt2Columns[cnt].back());
toFill--;
cnt2Columns[cnt].pop_back();
}
}
for(int cnt = 0;cnt<=(n-1)/2;cnt++)
{
while(toAdd[cnt].empty()==false)
{
cnt2Columns[cnt].push_back(toAdd[cnt].back());
toAdd[cnt].pop_back();
}
}
while(toAdd[(n+1)/2].empty()==false)
{
ruined.push_back(toAdd[(n+1)/2].back());
toAdd[(n+1)/2].pop_back();
}
int curr = row + 1;
for(int cnt = 0;cnt<=(n-1)/2;cnt++)
{
curr += cnt2Columns[cnt].size();
}
//cout << answer << " vs " << curr << '\n';
if(answer < curr)
{
answer = curr;
bestN = n;
bestM = m;
bestRows = row;
bestMode = mode;
}
}
return answer;
}
int n, m;
int recover()
{
if(bestMode==true)
{
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
matrix[i][j] = 1;
}
}
}
ruined.clear();
for(int i = 0;i<=max(bestN, bestM);i++)
{
toAdd[i].clear();
cnt2Columns[i].clear();
}
for(int j = 0;j<bestM;j++)
{
cnt2Columns[0].push_back(j);
}
for(int row = 0;row<=bestRows;row++)
{
int toFill = bestM/2 + 1;
for(int i = 0;i<ruined.size();i++)
{
toFill--;
if(bestMode==false) matrix[row][ ruined[i] ] = 1;
else matrix[ ruined[i] ][row] = 0;
if(toFill==0) break;
}
for(int cnt = 0;cnt<=(bestN-1)/2;cnt++)
{
while(toFill>0 && cnt2Columns[cnt].empty()==false)
{
if(bestMode==false) matrix[row][ cnt2Columns[cnt].back() ] = 1;
else matrix[ cnt2Columns[cnt].back() ][row] = 0;
toAdd[cnt+1].push_back(cnt2Columns[cnt].back());
toFill--;
cnt2Columns[cnt].pop_back();
}
}
for(int cnt = 0;cnt<=(bestN-1)/2;cnt++)
{
while(toAdd[cnt].empty()==false)
{
cnt2Columns[cnt].push_back(toAdd[cnt].back());
toAdd[cnt].pop_back();
}
}
while(toAdd[(bestN+1)/2].empty()==false)
{
ruined.push_back(toAdd[(bestN+1)/2].back());
toAdd[(bestN+1)/2].pop_back();
}
int curr = row + 1;
for(int cnt = 0;cnt<=(bestN-1)/2;cnt++)
{
curr += cnt2Columns[cnt].size();
}
}
}
int main()
{
int T;
cin >> T;
while(T--)
{
answer = 0;
memset(matrix, 0, sizeof(matrix));
cin >> n >> m;
myCalc(n, m, false);
myCalc(m, n, true);
recover();
//cout << n << " &&&&&& " << m << '\n';
//cout << answer << " -> " << bestN << " " << bestM << " " << bestRows << '\n';
cout << answer << '\n';
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
cout << ((matrix[i][j]==1)?'+':'-');
}
cout << '\n';
}
}
}
Compilation message
stones.cpp: In function 'int myCalc(int, int, bool)':
stones.cpp:114:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<ruined.size();i++)
~^~~~~~~~~~~~~~
stones.cpp: In function 'int recover()':
stones.cpp:193:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<ruined.size();i++)
~^~~~~~~~~~~~~~
stones.cpp:235:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
22 ms |
1400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
22 ms |
1400 KB |
Output is correct |
4 |
Correct |
35 ms |
1456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
93 ms |
2456 KB |
Output is correct |
2 |
Correct |
60 ms |
4984 KB |
Output is correct |
3 |
Correct |
59 ms |
5056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
72 ms |
2424 KB |
Output is correct |
2 |
Correct |
54 ms |
4472 KB |
Output is correct |
3 |
Correct |
49 ms |
3704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1400 KB |
Output is correct |
2 |
Correct |
4 ms |
1400 KB |
Output is correct |
3 |
Correct |
22 ms |
1400 KB |
Output is correct |
4 |
Correct |
35 ms |
1456 KB |
Output is correct |
5 |
Correct |
93 ms |
2456 KB |
Output is correct |
6 |
Correct |
60 ms |
4984 KB |
Output is correct |
7 |
Correct |
59 ms |
5056 KB |
Output is correct |
8 |
Correct |
72 ms |
2424 KB |
Output is correct |
9 |
Correct |
54 ms |
4472 KB |
Output is correct |
10 |
Correct |
49 ms |
3704 KB |
Output is correct |
11 |
Correct |
77 ms |
1656 KB |
Output is correct |
12 |
Correct |
56 ms |
4524 KB |
Output is correct |
13 |
Correct |
57 ms |
3960 KB |
Output is correct |
14 |
Correct |
43 ms |
3320 KB |
Output is correct |
15 |
Correct |
69 ms |
5444 KB |
Output is correct |
16 |
Correct |
50 ms |
4984 KB |
Output is correct |
17 |
Correct |
25 ms |
3576 KB |
Output is correct |