#include<iostream>
#include<cstring>
#include<random>
#include<vector>
#include<algorithm>
using namespace std;
int n, m;
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];
int bestN, bestM, bestRows;
bool matrix[1005][1005];
int myCalc(int n, int m)
{
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);
}
if(answer<m)
{
answer = m;
bestN = n;
bestM = m;
bestRows = -1;
}
for(int row = 0;row<n;row++)
{
/*
for(int cnt = 0;cnt<=row;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<=row;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();
}
if(answer<curr)
{
answer = curr;
bestN = n;
bestM = m;
bestRows = row;
}
}
return answer;
}
int recover()
{
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++)
{
/*
for(int cnt = 0;cnt<=row;cnt++)
{
cout << cnt << ":";
for(int x: cnt2Columns[cnt]) cout << " " << x;
cout << '\n';
}
cout << " ---- --- --- " << '\n';
*/
int toFill = bestM/2 + 1;
for(int i = 0;i<ruined.size();i++)
{
toFill--;
matrix[row][ ruined[i] ] = 1;
if(toFill==0) break;
}
for(int cnt = 0;cnt<=row;cnt++)
{
while(toFill>0 && cnt2Columns[cnt].empty()==false)
{
matrix[row][ cnt2Columns[cnt].back() ] = 1;
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);
myCalc(m, n);
recover();
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)':
stones.cpp:107: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:182:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<ruined.size();i++)
~^~~~~~~~~~~~~~
stones.cpp:221: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 |
21 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 |
21 ms |
1400 KB |
Output is correct |
4 |
Incorrect |
35 ms |
1452 KB |
in the table A+B is not equal to 40 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
86 ms |
2512 KB |
in the table A+B is not equal to 116 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
2424 KB |
Output is correct |
2 |
Correct |
56 ms |
4464 KB |
Output is correct |
3 |
Correct |
51 ms |
3832 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 |
21 ms |
1400 KB |
Output is correct |
4 |
Incorrect |
35 ms |
1452 KB |
in the table A+B is not equal to 40 |